sorcery.c: Sorcery enhancements for wizard management
[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 #include "asterisk/_private.h"
33 #include "asterisk/paths.h"     /* use ast_config_AST_SYSTEM_NAME */
34 #include <ctype.h>
35 #include <time.h>
36 #include <sys/time.h>
37 #if defined(HAVE_SYSINFO)
38 #include <sys/sysinfo.h>
39 #endif
40 #if defined(SOLARIS)
41 #include <sys/loadavg.h>
42 #endif
43
44 #include "asterisk/lock.h"
45 #include "asterisk/cli.h"
46 #include "asterisk/pbx.h"
47 #include "asterisk/channel.h"
48 #include "asterisk/file.h"
49 #include "asterisk/callerid.h"
50 #include "asterisk/cdr.h"
51 #include "asterisk/config.h"
52 #include "asterisk/term.h"
53 #include "asterisk/time.h"
54 #include "asterisk/manager.h"
55 #include "asterisk/ast_expr.h"
56 #include "asterisk/linkedlists.h"
57 #define SAY_STUBS       /* generate declarations and stubs for say methods */
58 #include "asterisk/say.h"
59 #include "asterisk/utils.h"
60 #include "asterisk/causes.h"
61 #include "asterisk/musiconhold.h"
62 #include "asterisk/app.h"
63 #include "asterisk/devicestate.h"
64 #include "asterisk/presencestate.h"
65 #include "asterisk/hashtab.h"
66 #include "asterisk/module.h"
67 #include "asterisk/indications.h"
68 #include "asterisk/taskprocessor.h"
69 #include "asterisk/xmldoc.h"
70 #include "asterisk/astobj2.h"
71 #include "asterisk/stasis_channels.h"
72 #include "asterisk/dial.h"
73 #include "asterisk/vector.h"
74 #include "pbx_private.h"
75
76 /*!
77  * \note I M P O R T A N T :
78  *
79  *              The speed of extension handling will likely be among the most important
80  * aspects of this PBX.  The switching scheme as it exists right now isn't
81  * terribly bad (it's O(N+M), where N is the # of extensions and M is the avg #
82  * of priorities, but a constant search time here would be great ;-)
83  *
84  * A new algorithm to do searching based on a 'compiled' pattern tree is introduced
85  * here, and shows a fairly flat (constant) search time, even for over
86  * 10000 patterns.
87  *
88  * Also, using a hash table for context/priority name lookup can help prevent
89  * the find_extension routines from absorbing exponential cpu cycles as the number
90  * of contexts/priorities grow. I've previously tested find_extension with red-black trees,
91  * which have O(log2(n)) speed. Right now, I'm using hash tables, which do
92  * searches (ideally) in O(1) time. While these techniques do not yield much
93  * speed in small dialplans, they are worth the trouble in large dialplans.
94  *
95  */
96
97 /*** DOCUMENTATION
98         <function name="EXCEPTION" language="en_US">
99                 <synopsis>
100                         Retrieve the details of the current dialplan exception.
101                 </synopsis>
102                 <syntax>
103                         <parameter name="field" required="true">
104                                 <para>The following fields are available for retrieval:</para>
105                                 <enumlist>
106                                         <enum name="reason">
107                                                 <para>INVALID, ERROR, RESPONSETIMEOUT, ABSOLUTETIMEOUT, or custom
108                                                 value set by the RaiseException() application</para>
109                                         </enum>
110                                         <enum name="context">
111                                                 <para>The context executing when the exception occurred.</para>
112                                         </enum>
113                                         <enum name="exten">
114                                                 <para>The extension executing when the exception occurred.</para>
115                                         </enum>
116                                         <enum name="priority">
117                                                 <para>The numeric priority executing when the exception occurred.</para>
118                                         </enum>
119                                 </enumlist>
120                         </parameter>
121                 </syntax>
122                 <description>
123                         <para>Retrieve the details (specified <replaceable>field</replaceable>) of the current dialplan exception.</para>
124                 </description>
125                 <see-also>
126                         <ref type="application">RaiseException</ref>
127                 </see-also>
128         </function>
129         <function name="TESTTIME" language="en_US">
130                 <synopsis>
131                         Sets a time to be used with the channel to test logical conditions.
132                 </synopsis>
133                 <syntax>
134                         <parameter name="date" required="true" argsep=" ">
135                                 <para>Date in ISO 8601 format</para>
136                         </parameter>
137                         <parameter name="time" required="true" argsep=" ">
138                                 <para>Time in HH:MM:SS format (24-hour time)</para>
139                         </parameter>
140                         <parameter name="zone" required="false">
141                                 <para>Timezone name</para>
142                         </parameter>
143                 </syntax>
144                 <description>
145                         <para>To test dialplan timing conditions at times other than the current time, use
146                         this function to set an alternate date and time.  For example, you may wish to evaluate
147                         whether a location will correctly identify to callers that the area is closed on Christmas
148                         Day, when Christmas would otherwise fall on a day when the office is normally open.</para>
149                 </description>
150                 <see-also>
151                         <ref type="application">GotoIfTime</ref>
152                 </see-also>
153         </function>
154         <manager name="ShowDialPlan" language="en_US">
155                 <synopsis>
156                         Show dialplan contexts and extensions
157                 </synopsis>
158                 <syntax>
159                         <xi:include xpointer="xpointer(/docs/manager[@name='Login']/syntax/parameter[@name='ActionID'])" />
160                         <parameter name="Extension">
161                                 <para>Show a specific extension.</para>
162                         </parameter>
163                         <parameter name="Context">
164                                 <para>Show a specific context.</para>
165                         </parameter>
166                 </syntax>
167                 <description>
168                         <para>Show dialplan contexts and extensions. Be aware that showing the full dialplan
169                         may take a lot of capacity.</para>
170                 </description>
171         </manager>
172         <manager name="ExtensionStateList" language="en_US">
173                 <synopsis>
174                         List the current known extension states.
175                 </synopsis>
176                 <syntax>
177                         <xi:include xpointer="xpointer(/docs/manager[@name='Login']/syntax/parameter[@name='ActionID'])" />
178                 </syntax>
179                 <description>
180                         <para>This will list out all known extension states in a
181                         sequence of <replaceable>ExtensionStatus</replaceable> events.
182                         When finished, a <replaceable>ExtensionStateListComplete</replaceable> event
183                         will be emitted.</para>
184                 </description>
185                 <see-also>
186                         <ref type="manager">ExtensionState</ref>
187                         <ref type="function">HINT</ref>
188                         <ref type="function">EXTENSION_STATE</ref>
189                 </see-also>
190                 <responses>
191                         <list-elements>
192                                 <xi:include xpointer="xpointer(/docs/managerEvent[@name='ExtensionStatus'])" />
193                         </list-elements>
194                         <managerEvent name="ExtensionStateListComplete" language="en_US">
195                                 <managerEventInstance class="EVENT_FLAG_COMMAND">
196                                         <synopsis>
197                                                 Indicates the end of the list the current known extension states.
198                                         </synopsis>
199                                         <syntax>
200                                                 <parameter name="EventList">
201                                                         <para>Conveys the status of the event list.</para>
202                                                 </parameter>
203                                                 <parameter name="ListItems">
204                                                         <para>Conveys the number of statuses reported.</para>
205                                                 </parameter>
206                                         </syntax>
207                                 </managerEventInstance>
208                         </managerEvent>
209                 </responses>
210         </manager>
211  ***/
212
213 #ifdef LOW_MEMORY
214 #define EXT_DATA_SIZE 256
215 #else
216 #define EXT_DATA_SIZE 8192
217 #endif
218
219 #define SWITCH_DATA_LENGTH 256
220
221 #define VAR_NORMAL              1
222 #define VAR_SOFTTRAN    2
223 #define VAR_HARDTRAN    3
224
225 struct ast_context;
226 struct ast_app;
227
228 AST_THREADSTORAGE(switch_data);
229 AST_THREADSTORAGE(extensionstate_buf);
230
231 /*!
232    \brief ast_exten: An extension
233         The dialplan is saved as a linked list with each context
234         having it's own linked list of extensions - one item per
235         priority.
236 */
237 struct ast_exten {
238         char *exten;                    /*!< Clean Extension id */
239         char *name;                     /*!< Extension name (may include '-' eye candy) */
240         int matchcid;                   /*!< Match caller id ? */
241         const char *cidmatch;           /*!< Caller id to match for this extension */
242         const char *cidmatch_display;   /*!< Caller id to match (display version) */
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         const char *registrar_file;     /*!< File name used to register extension */
255         int registrar_line;             /*!< Line number the extension was registered in text */
256         struct ast_exten *next;         /*!< Extension with a greater ID */
257         char stuff[0];
258 };
259
260 /*! \brief match_char: forms a syntax tree for quick matching of extension patterns */
261 struct match_char
262 {
263         int is_pattern; /* the pattern started with '_' */
264         int deleted;    /* if this is set, then... don't return it */
265         int specificity; /* simply the strlen of x, or 10 for X, 9 for Z, and 8 for N; and '.' and '!' will add 11 ? */
266         struct match_char *alt_char;
267         struct match_char *next_char;
268         struct ast_exten *exten; /* attached to last char of a pattern for exten */
269         char x[1];       /* the pattern itself-- matches a single char */
270 };
271
272 struct scoreboard  /* make sure all fields are 0 before calling new_find_extension */
273 {
274         int total_specificity;
275         int total_length;
276         char last_char;   /* set to ! or . if they are the end of the pattern */
277         int canmatch;     /* if the string to match was just too short */
278         struct match_char *node;
279         struct ast_exten *canmatch_exten;
280         struct ast_exten *exten;
281 };
282
283 /*! \brief ast_context: An extension context - must remain in sync with fake_context */
284 struct ast_context {
285         ast_rwlock_t lock;                      /*!< A lock to prevent multiple threads from clobbering the context */
286         struct ast_exten *root;                 /*!< The root of the list of extensions */
287         struct ast_hashtab *root_table;            /*!< For exact matches on the extensions in the pattern tree, and for traversals of the pattern_tree  */
288         struct match_char *pattern_tree;        /*!< A tree to speed up extension pattern matching */
289         struct ast_context *next;               /*!< Link them together */
290         struct ast_includes includes;           /*!< Include other contexts */
291         struct ast_ignorepats ignorepats;       /*!< Patterns for which to continue playing dialtone */
292         struct ast_sws alts;                    /*!< Alternative switches */
293         char *registrar;                        /*!< Registrar -- make sure you malloc this, as the registrar may have to survive module unloads */
294         int refcount;                   /*!< each module that would have created this context should inc/dec this as appropriate */
295         int autohints;                  /*!< Whether autohints support is enabled or not */
296         ast_mutex_t macrolock;                  /*!< A lock to implement "exclusive" macros - held whilst a call is executing in the macro */
297         char name[0];                           /*!< Name of the context */
298 };
299
300 /*! \brief ast_state_cb: An extension state notify register item */
301 struct ast_state_cb {
302         /*! Watcher ID returned when registered. */
303         int id;
304         /*! Arbitrary data passed for callbacks. */
305         void *data;
306         /*! Flag if this callback is an extended callback containing detailed device status */
307         int extended;
308         /*! Callback when state changes. */
309         ast_state_cb_type change_cb;
310         /*! Callback when destroyed so any resources given by the registerer can be freed. */
311         ast_state_cb_destroy_type destroy_cb;
312         /*! \note Only used by ast_merge_contexts_and_delete */
313         AST_LIST_ENTRY(ast_state_cb) entry;
314 };
315
316 /*!
317  * \brief Structure for dial plan hints
318  *
319  * \note Hints are pointers from an extension in the dialplan to
320  * one or more devices (tech/name)
321  *
322  * See \ref AstExtState
323  */
324 struct ast_hint {
325         /*!
326          * \brief Hint extension
327          *
328          * \note
329          * Will never be NULL while the hint is in the hints container.
330          */
331         struct ast_exten *exten;
332         struct ao2_container *callbacks; /*!< Device state callback container for this extension */
333
334         /*! Dev state variables */
335         int laststate;                  /*!< Last known device state */
336
337         /*! Presence state variables */
338         int last_presence_state;     /*!< Last known presence state */
339         char *last_presence_subtype; /*!< Last known presence subtype string */
340         char *last_presence_message; /*!< Last known presence message string */
341
342         char context_name[AST_MAX_CONTEXT];/*!< Context of destroyed hint extension. */
343         char exten_name[AST_MAX_EXTENSION];/*!< Extension of destroyed hint extension. */
344
345         AST_VECTOR(, char *) devices; /*!< Devices associated with the hint */
346 };
347
348 STASIS_MESSAGE_TYPE_DEFN_LOCAL(hint_change_message_type);
349 STASIS_MESSAGE_TYPE_DEFN_LOCAL(hint_remove_message_type);
350
351 #define HINTDEVICE_DATA_LENGTH 16
352 AST_THREADSTORAGE(hintdevice_data);
353
354 /* --- Hash tables of various objects --------*/
355 #ifdef LOW_MEMORY
356 #define HASH_EXTENHINT_SIZE 17
357 #else
358 #define HASH_EXTENHINT_SIZE 563
359 #endif
360
361
362 /*! \brief Container for hint devices */
363 static struct ao2_container *hintdevices;
364
365 /*!
366  * \brief Structure for dial plan hint devices
367  * \note hintdevice is one device pointing to a hint.
368  */
369 struct ast_hintdevice {
370         /*!
371          * \brief Hint this hintdevice belongs to.
372          * \note Holds a reference to the hint object.
373          */
374         struct ast_hint *hint;
375         /*! Name of the hint device. */
376         char hintdevice[1];
377 };
378
379 /*! \brief Container for autohint contexts */
380 static struct ao2_container *autohints;
381
382 /*!
383  * \brief Structure for dial plan autohints
384  */
385 struct ast_autohint {
386         /*! \brief Name of the registrar */
387         char *registrar;
388         /*! \brief Name of the context */
389         char context[1];
390 };
391
392 /*!
393  * \note Using the device for hash
394  */
395 static int hintdevice_hash_cb(const void *obj, const int flags)
396 {
397         const struct ast_hintdevice *ext;
398         const char *key;
399
400         switch (flags & OBJ_SEARCH_MASK) {
401         case OBJ_SEARCH_KEY:
402                 key = obj;
403                 break;
404         case OBJ_SEARCH_OBJECT:
405                 ext = obj;
406                 key = ext->hintdevice;
407                 break;
408         default:
409                 ast_assert(0);
410                 return 0;
411         }
412
413         return ast_str_case_hash(key);
414 }
415
416 /*!
417  * \note Devices on hints are not unique so no CMP_STOP is returned
418  * Dont use ao2_find against hintdevices container cause there always
419  * could be more than one result.
420  */
421 static int hintdevice_cmp_multiple(void *obj, void *arg, int flags)
422 {
423         struct ast_hintdevice *left = obj;
424         struct ast_hintdevice *right = arg;
425         const char *right_key = arg;
426         int cmp;
427
428         switch (flags & OBJ_SEARCH_MASK) {
429         case OBJ_SEARCH_OBJECT:
430                 right_key = right->hintdevice;
431                 /* Fall through */
432         case OBJ_SEARCH_KEY:
433                 cmp = strcasecmp(left->hintdevice, right_key);
434                 break;
435         case OBJ_SEARCH_PARTIAL_KEY:
436                 /*
437                 * We could also use a partial key struct containing a length
438                 * so strlen() does not get called for every comparison instead.
439                 */
440                 cmp = strncmp(left->hintdevice, right_key, strlen(right_key));
441                 break;
442         default:
443                 ast_assert(0);
444                 cmp = 0;
445                 break;
446         }
447         return cmp ? 0 : CMP_MATCH;
448 }
449
450 /*!
451  * \note Using the context name for hash
452  */
453 static int autohint_hash_cb(const void *obj, const int flags)
454 {
455         const struct ast_autohint *autohint;
456         const char *key;
457
458         switch (flags & OBJ_SEARCH_MASK) {
459         case OBJ_SEARCH_KEY:
460                 key = obj;
461                 break;
462         case OBJ_SEARCH_OBJECT:
463                 autohint = obj;
464                 key = autohint->context;
465                 break;
466         default:
467                 ast_assert(0);
468                 return 0;
469         }
470
471         return ast_str_case_hash(key);
472 }
473
474 static int autohint_cmp(void *obj, void *arg, int flags)
475 {
476         struct ast_autohint *left = obj;
477         struct ast_autohint *right = arg;
478         const char *right_key = arg;
479         int cmp;
480
481         switch (flags & OBJ_SEARCH_MASK) {
482         case OBJ_SEARCH_OBJECT:
483                 right_key = right->context;
484                 /* Fall through */
485         case OBJ_SEARCH_KEY:
486                 cmp = strcasecmp(left->context, right_key);
487                 break;
488         case OBJ_SEARCH_PARTIAL_KEY:
489                 /*
490                 * We could also use a partial key struct containing a length
491                 * so strlen() does not get called for every comparison instead.
492                 */
493                 cmp = strncmp(left->context, right_key, strlen(right_key));
494                 break;
495         default:
496                 ast_assert(0);
497                 cmp = 0;
498                 break;
499         }
500         return cmp ? 0 : CMP_MATCH | CMP_STOP;
501 }
502
503 /*! \internal \brief \c ao2_callback function to remove hintdevices */
504 static int hintdevice_remove_cb(void *obj, void *arg, void *data, int flags)
505 {
506         struct ast_hintdevice *candidate = obj;
507         char *device = arg;
508         struct ast_hint *hint = data;
509
510         if (!strcasecmp(candidate->hintdevice, device)
511                 && candidate->hint == hint) {
512                 return CMP_MATCH;
513         }
514         return 0;
515 }
516
517 static int remove_hintdevice(struct ast_hint *hint)
518 {
519         while (AST_VECTOR_SIZE(&hint->devices) > 0) {
520                 char *device = AST_VECTOR_GET(&hint->devices, 0);
521
522                 ao2_t_callback_data(hintdevices, OBJ_SEARCH_KEY | OBJ_UNLINK | OBJ_NODATA,
523                         hintdevice_remove_cb, device, hint, "Remove device from container");
524                 AST_VECTOR_REMOVE_UNORDERED(&hint->devices, 0);
525                 ast_free(device);
526         }
527
528         return 0;
529 }
530
531 static char *parse_hint_device(struct ast_str *hint_args);
532 /*!
533  * \internal
534  * \brief Destroy the given hintdevice object.
535  *
536  * \param obj Hint device to destroy.
537  *
538  * \return Nothing
539  */
540 static void hintdevice_destroy(void *obj)
541 {
542         struct ast_hintdevice *doomed = obj;
543
544         if (doomed->hint) {
545                 ao2_ref(doomed->hint, -1);
546                 doomed->hint = NULL;
547         }
548 }
549
550 /*! \brief add hintdevice structure and link it into the container.
551  */
552 static int add_hintdevice(struct ast_hint *hint, const char *devicelist)
553 {
554         struct ast_str *str;
555         char *parse;
556         char *cur;
557         struct ast_hintdevice *device;
558         int devicelength;
559
560         if (!hint || !devicelist) {
561                 /* Trying to add garbage? Don't bother. */
562                 return 0;
563         }
564         if (!(str = ast_str_thread_get(&hintdevice_data, 16))) {
565                 return -1;
566         }
567         ast_str_set(&str, 0, "%s", devicelist);
568         parse = ast_str_buffer(str);
569
570         /* Spit on '&' and ',' to handle presence hints as well */
571         while ((cur = strsep(&parse, "&,"))) {
572                 char *device_name;
573
574                 devicelength = strlen(cur);
575                 if (!devicelength) {
576                         continue;
577                 }
578
579                 device_name = ast_strdup(cur);
580                 if (!device_name) {
581                         return -1;
582                 }
583
584                 device = ao2_t_alloc(sizeof(*device) + devicelength, hintdevice_destroy,
585                         "allocating a hintdevice structure");
586                 if (!device) {
587                         ast_free(device_name);
588                         return -1;
589                 }
590                 strcpy(device->hintdevice, cur);
591                 ao2_ref(hint, +1);
592                 device->hint = hint;
593                 if (AST_VECTOR_APPEND(&hint->devices, device_name)) {
594                         ast_free(device_name);
595                         ao2_ref(device, -1);
596                         return -1;
597                 }
598                 ao2_t_link(hintdevices, device, "Linking device into hintdevice container.");
599                 ao2_t_ref(device, -1, "hintdevice is linked so we can unref");
600         }
601
602         return 0;
603 }
604
605
606 static const struct cfextension_states {
607         int extension_state;
608         const char * const text;
609 } extension_states[] = {
610         { AST_EXTENSION_NOT_INUSE,                     "Idle" },
611         { AST_EXTENSION_INUSE,                         "InUse" },
612         { AST_EXTENSION_BUSY,                          "Busy" },
613         { AST_EXTENSION_UNAVAILABLE,                   "Unavailable" },
614         { AST_EXTENSION_RINGING,                       "Ringing" },
615         { AST_EXTENSION_INUSE | AST_EXTENSION_RINGING, "InUse&Ringing" },
616         { AST_EXTENSION_ONHOLD,                        "Hold" },
617         { AST_EXTENSION_INUSE | AST_EXTENSION_ONHOLD,  "InUse&Hold" }
618 };
619
620 struct pbx_exception {
621         AST_DECLARE_STRING_FIELDS(
622                 AST_STRING_FIELD(context);      /*!< Context associated with this exception */
623                 AST_STRING_FIELD(exten);        /*!< Exten associated with this exception */
624                 AST_STRING_FIELD(reason);               /*!< The exception reason */
625         );
626
627         int priority;                           /*!< Priority associated with this exception */
628 };
629
630 static int matchcid(const char *cidpattern, const char *callerid);
631 #ifdef NEED_DEBUG
632 static void log_match_char_tree(struct match_char *node, char *prefix); /* for use anywhere */
633 #endif
634 static void new_find_extension(const char *str, struct scoreboard *score,
635                 struct match_char *tree, int length, int spec, const char *callerid,
636                 const char *label, enum ext_match_t action);
637 static struct match_char *already_in_tree(struct match_char *current, char *pat, int is_pattern);
638 static struct match_char *add_exten_to_pattern_tree(struct ast_context *con,
639                 struct ast_exten *e1, int findonly);
640 static void create_match_char_tree(struct ast_context *con);
641 static struct ast_exten *get_canmatch_exten(struct match_char *node);
642 static void destroy_pattern_tree(struct match_char *pattern_tree);
643 static int hashtab_compare_extens(const void *ha_a, const void *ah_b);
644 static int hashtab_compare_exten_numbers(const void *ah_a, const void *ah_b);
645 static int hashtab_compare_exten_labels(const void *ah_a, const void *ah_b);
646 static unsigned int hashtab_hash_extens(const void *obj);
647 static unsigned int hashtab_hash_priority(const void *obj);
648 static unsigned int hashtab_hash_labels(const void *obj);
649 static void __ast_internal_context_destroy( struct ast_context *con);
650 static int ast_add_extension_nolock(const char *context, int replace, const char *extension,
651         int priority, const char *label, const char *callerid,
652         const char *application, void *data, void (*datad)(void *), const char *registrar);
653 static int ast_add_extension2_lockopt(struct ast_context *con,
654         int replace, const char *extension, int priority, const char *label, const char *callerid,
655         const char *application, void *data, void (*datad)(void *),
656         const char *registrar, const char *registrar_file, int registrar_line,
657         int lock_context);
658 static struct ast_context *find_context_locked(const char *context);
659 static struct ast_context *find_context(const char *context);
660 static void get_device_state_causing_channels(struct ao2_container *c);
661 static unsigned int ext_strncpy(char *dst, const char *src, size_t dst_size, int nofluff);
662
663 /*!
664  * \internal
665  * \brief Character array comparison function for qsort.
666  *
667  * \param a Left side object.
668  * \param b Right side object.
669  *
670  * \retval <0 if a < b
671  * \retval =0 if a = b
672  * \retval >0 if a > b
673  */
674 static int compare_char(const void *a, const void *b)
675 {
676         const unsigned char *ac = a;
677         const unsigned char *bc = b;
678
679         return *ac - *bc;
680 }
681
682 /* labels, contexts are case sensitive  priority numbers are ints */
683 int ast_hashtab_compare_contexts(const void *ah_a, const void *ah_b)
684 {
685         const struct ast_context *ac = ah_a;
686         const struct ast_context *bc = ah_b;
687         if (!ac || !bc) /* safety valve, but it might prevent a crash you'd rather have happen */
688                 return 1;
689         /* assume context names are registered in a string table! */
690         return strcmp(ac->name, bc->name);
691 }
692
693 static int hashtab_compare_extens(const void *ah_a, const void *ah_b)
694 {
695         const struct ast_exten *ac = ah_a;
696         const struct ast_exten *bc = ah_b;
697         int x = strcmp(ac->exten, bc->exten);
698         if (x) { /* if exten names are diff, then return */
699                 return x;
700         }
701
702         /* but if they are the same, do the cidmatch values match? */
703         /* not sure which side may be using ast_ext_matchcid_types, so check both */
704         if (ac->matchcid == AST_EXT_MATCHCID_ANY || bc->matchcid == AST_EXT_MATCHCID_ANY) {
705                 return 0;
706         }
707         if (ac->matchcid == AST_EXT_MATCHCID_OFF && bc->matchcid == AST_EXT_MATCHCID_OFF) {
708                 return 0;
709         }
710         if (ac->matchcid != bc->matchcid) {
711                 return 1;
712         }
713         /* all other cases already disposed of, match now required on callerid string (cidmatch) */
714         /* although ast_add_extension2_lockopt() enforces non-zero ptr, caller may not have */
715         if (ast_strlen_zero(ac->cidmatch) && ast_strlen_zero(bc->cidmatch)) {
716                 return 0;
717         }
718         return strcmp(ac->cidmatch, bc->cidmatch);
719 }
720
721 static int hashtab_compare_exten_numbers(const void *ah_a, const void *ah_b)
722 {
723         const struct ast_exten *ac = ah_a;
724         const struct ast_exten *bc = ah_b;
725         return ac->priority != bc->priority;
726 }
727
728 static int hashtab_compare_exten_labels(const void *ah_a, const void *ah_b)
729 {
730         const struct ast_exten *ac = ah_a;
731         const struct ast_exten *bc = ah_b;
732         return strcmp(S_OR(ac->label, ""), S_OR(bc->label, ""));
733 }
734
735 unsigned int ast_hashtab_hash_contexts(const void *obj)
736 {
737         const struct ast_context *ac = obj;
738         return ast_hashtab_hash_string(ac->name);
739 }
740
741 static unsigned int hashtab_hash_extens(const void *obj)
742 {
743         const struct ast_exten *ac = obj;
744         unsigned int x = ast_hashtab_hash_string(ac->exten);
745         unsigned int y = 0;
746         if (ac->matchcid == AST_EXT_MATCHCID_ON)
747                 y = ast_hashtab_hash_string(ac->cidmatch);
748         return x+y;
749 }
750
751 static unsigned int hashtab_hash_priority(const void *obj)
752 {
753         const struct ast_exten *ac = obj;
754         return ast_hashtab_hash_int(ac->priority);
755 }
756
757 static unsigned int hashtab_hash_labels(const void *obj)
758 {
759         const struct ast_exten *ac = obj;
760         return ast_hashtab_hash_string(S_OR(ac->label, ""));
761 }
762
763 static int autofallthrough = 1;
764 static int extenpatternmatchnew = 0;
765 static char *overrideswitch = NULL;
766
767 /*! \brief Subscription for device state change events */
768 static struct stasis_subscription *device_state_sub;
769 /*! \brief Subscription for presence state change events */
770 static struct stasis_subscription *presence_state_sub;
771
772 AST_MUTEX_DEFINE_STATIC(maxcalllock);
773 static int countcalls;
774 static int totalcalls;
775
776 static struct ast_context *contexts;
777 static struct ast_hashtab *contexts_table = NULL;
778
779 /*!
780  * \brief Lock for the ast_context list
781  * \note
782  * This lock MUST be recursive, or a deadlock on reload may result.  See
783  * https://issues.asterisk.org/view.php?id=17643
784  */
785 AST_MUTEX_DEFINE_STATIC(conlock);
786
787 /*!
788  * \brief Lock to hold off restructuring of hints by ast_merge_contexts_and_delete.
789  */
790 AST_MUTEX_DEFINE_STATIC(context_merge_lock);
791
792 static int stateid = 1;
793 /*!
794  * \note When holding this container's lock, do _not_ do
795  * anything that will cause conlock to be taken, unless you
796  * _already_ hold it.  The ast_merge_contexts_and_delete function
797  * will take the locks in conlock/hints order, so any other
798  * paths that require both locks must also take them in that
799  * order.
800  */
801 static struct ao2_container *hints;
802
803 static struct ao2_container *statecbs;
804
805 #ifdef CONTEXT_DEBUG
806
807 /* these routines are provided for doing run-time checks
808    on the extension structures, in case you are having
809    problems, this routine might help you localize where
810    the problem is occurring. It's kinda like a debug memory
811    allocator's arena checker... It'll eat up your cpu cycles!
812    but you'll see, if you call it in the right places,
813    right where your problems began...
814 */
815
816 /* you can break on the check_contexts_trouble()
817 routine in your debugger to stop at the moment
818 there's a problem */
819 void check_contexts_trouble(void);
820
821 void check_contexts_trouble(void)
822 {
823         int x = 1;
824         x = 2;
825 }
826
827 int check_contexts(char *, int);
828
829 int check_contexts(char *file, int line )
830 {
831         struct ast_hashtab_iter *t1;
832         struct ast_context *c1, *c2;
833         int found = 0;
834         struct ast_exten *e1, *e2, *e3;
835         struct ast_exten ex;
836
837         /* try to find inconsistencies */
838         /* is every context in the context table in the context list and vice-versa ? */
839
840         if (!contexts_table) {
841                 ast_log(LOG_NOTICE,"Called from: %s:%d: No contexts_table!\n", file, line);
842                 usleep(500000);
843         }
844
845         t1 = ast_hashtab_start_traversal(contexts_table);
846         while( (c1 = ast_hashtab_next(t1))) {
847                 for(c2=contexts;c2;c2=c2->next) {
848                         if (!strcmp(c1->name, c2->name)) {
849                                 found = 1;
850                                 break;
851                         }
852                 }
853                 if (!found) {
854                         ast_log(LOG_NOTICE,"Called from: %s:%d: Could not find the %s context in the linked list\n", file, line, c1->name);
855                         check_contexts_trouble();
856                 }
857         }
858         ast_hashtab_end_traversal(t1);
859         for(c2=contexts;c2;c2=c2->next) {
860                 c1 = find_context_locked(c2->name);
861                 if (!c1) {
862                         ast_log(LOG_NOTICE,"Called from: %s:%d: Could not find the %s context in the hashtab\n", file, line, c2->name);
863                         check_contexts_trouble();
864                 } else
865                         ast_unlock_contexts();
866         }
867
868         /* loop thru all contexts, and verify the exten structure compares to the
869            hashtab structure */
870         for(c2=contexts;c2;c2=c2->next) {
871                 c1 = find_context_locked(c2->name);
872                 if (c1) {
873                         ast_unlock_contexts();
874
875                         /* is every entry in the root list also in the root_table? */
876                         for(e1 = c1->root; e1; e1=e1->next)
877                         {
878                                 char dummy_name[1024];
879                                 ex.exten = dummy_name;
880                                 ex.matchcid = e1->matchcid;
881                                 ex.cidmatch = e1->cidmatch;
882                                 ast_copy_string(dummy_name, e1->exten, sizeof(dummy_name));
883                                 e2 = ast_hashtab_lookup(c1->root_table, &ex);
884                                 if (!e2) {
885                                         if (e1->matchcid == AST_EXT_MATCHCID_ON) {
886                                                 ast_log(LOG_NOTICE, "Called from: %s:%d: The %s context records "
887                                                         "the exten %s (CID match: %s) but it is not in its root_table\n",
888                                                         file, line, c2->name, dummy_name, e1->cidmatch_display);
889                                         } else {
890                                                 ast_log(LOG_NOTICE, "Called from: %s:%d: The %s context records "
891                                                         "the exten %s but it is not in its root_table\n",
892                                                         file, line, c2->name, dummy_name);
893                                         }
894                                         check_contexts_trouble();
895                                 }
896                         }
897
898                         /* is every entry in the root_table also in the root list? */
899                         if (!c2->root_table) {
900                                 if (c2->root) {
901                                         ast_log(LOG_NOTICE,"Called from: %s:%d: No c2->root_table for context %s!\n", file, line, c2->name);
902                                         usleep(500000);
903                                 }
904                         } else {
905                                 t1 = ast_hashtab_start_traversal(c2->root_table);
906                                 while( (e2 = ast_hashtab_next(t1)) ) {
907                                         for(e1=c2->root;e1;e1=e1->next) {
908                                                 if (!strcmp(e1->exten, e2->exten)) {
909                                                         found = 1;
910                                                         break;
911                                                 }
912                                         }
913                                         if (!found) {
914                                                 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);
915                                                 check_contexts_trouble();
916                                         }
917
918                                 }
919                                 ast_hashtab_end_traversal(t1);
920                         }
921                 }
922                 /* is every priority reflected in the peer_table at the head of the list? */
923
924                 /* is every entry in the root list also in the root_table? */
925                 /* are the per-extension peer_tables in the right place? */
926
927                 for(e1 = c2->root; e1; e1 = e1->next) {
928
929                         for(e2=e1;e2;e2=e2->peer) {
930                                 ex.priority = e2->priority;
931                                 if (e2 != e1 && e2->peer_table) {
932                                         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 );
933                                         check_contexts_trouble();
934                                 }
935
936                                 if (e2 != e1 && e2->peer_label_table) {
937                                         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 );
938                                         check_contexts_trouble();
939                                 }
940
941                                 if (e2 == e1 && !e2->peer_table){
942                                         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 );
943                                         check_contexts_trouble();
944                                 }
945
946                                 if (e2 == e1 && !e2->peer_label_table) {
947                                         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 );
948                                         check_contexts_trouble();
949                                 }
950
951
952                                 e3 = ast_hashtab_lookup(e1->peer_table, &ex);
953                                 if (!e3) {
954                                         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 );
955                                         check_contexts_trouble();
956                                 }
957                         }
958
959                         if (!e1->peer_table){
960                                 ast_log(LOG_NOTICE,"Called from: %s:%d: No e1->peer_table!\n", file, line);
961                                 usleep(500000);
962                         }
963
964                         /* is every entry in the peer_table also in the peer list? */
965                         t1 = ast_hashtab_start_traversal(e1->peer_table);
966                         while( (e2 = ast_hashtab_next(t1)) ) {
967                                 for(e3=e1;e3;e3=e3->peer) {
968                                         if (e3->priority == e2->priority) {
969                                                 found = 1;
970                                                 break;
971                                         }
972                                 }
973                                 if (!found) {
974                                         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 );
975                                         check_contexts_trouble();
976                                 }
977                         }
978                         ast_hashtab_end_traversal(t1);
979                 }
980         }
981         return 0;
982 }
983 #endif
984
985 static void pbx_destroy(struct ast_pbx *p)
986 {
987         ast_free(p);
988 }
989
990 /* form a tree that fully describes all the patterns in a context's extensions
991  * in this tree, a "node" represents an individual character or character set
992  * meant to match the corresponding character in a dial string. The tree
993  * consists of a series of match_char structs linked in a chain
994  * via the alt_char pointers. More than one pattern can share the same parts of the
995  * tree as other extensions with the same pattern to that point.
996  * My first attempt to duplicate the finding of the 'best' pattern was flawed in that
997  * I misunderstood the general algorithm. I thought that the 'best' pattern
998  * was the one with lowest total score. This was not true. Thus, if you have
999  * patterns "1XXXXX" and "X11111", you would be tempted to say that "X11111" is
1000  * the "best" match because it has fewer X's, and is therefore more specific,
1001  * but this is not how the old algorithm works. It sorts matching patterns
1002  * in a similar collating sequence as sorting alphabetic strings, from left to
1003  * right. Thus, "1XXXXX" comes before "X11111", and would be the "better" match,
1004  * because "1" is more specific than "X".
1005  * So, to accomodate this philosophy, I sort the tree branches along the alt_char
1006  * line so they are lowest to highest in specificity numbers. This way, as soon
1007  * as we encounter our first complete match, we automatically have the "best"
1008  * match and can stop the traversal immediately. Same for CANMATCH/MATCHMORE.
1009  * If anyone would like to resurrect the "wrong" pattern trie searching algorithm,
1010  * they are welcome to revert pbx to before 1 Apr 2008.
1011  * As an example, consider these 4 extensions:
1012  * (a) NXXNXXXXXX
1013  * (b) 307754XXXX
1014  * (c) fax
1015  * (d) NXXXXXXXXX
1016  *
1017  * In the above, between (a) and (d), (a) is a more specific pattern than (d), and would win over
1018  * most numbers. For all numbers beginning with 307754, (b) should always win.
1019  *
1020  * These pattern should form a (sorted) tree that looks like this:
1021  *   { "3" }  --next-->  { "0" }  --next--> { "7" } --next--> { "7" } --next--> { "5" } ... blah ... --> { "X" exten_match: (b) }
1022  *      |
1023  *      |alt
1024  *      |
1025  *   { "f" }  --next-->  { "a" }  --next--> { "x"  exten_match: (c) }
1026  *   { "N" }  --next-->  { "X" }  --next--> { "X" } --next--> { "N" } --next--> { "X" } ... blah ... --> { "X" exten_match: (a) }
1027  *      |                                                        |
1028  *      |                                                        |alt
1029  *      |alt                                                     |
1030  *      |                                                     { "X" } --next--> { "X" } ... blah ... --> { "X" exten_match: (d) }
1031  *      |
1032  *     NULL
1033  *
1034  *   In the above, I could easily turn "N" into "23456789", but I think that a quick "if( *z >= '2' && *z <= '9' )" might take
1035  *   fewer CPU cycles than a call to strchr("23456789",*z), where *z is the char to match...
1036  *
1037  *   traversal is pretty simple: one routine merely traverses the alt list, and for each matching char in the pattern,  it calls itself
1038  *   on the corresponding next pointer, incrementing also the pointer of the string to be matched, and passing the total specificity and length.
1039  *   We pass a pointer to a scoreboard down through, also.
1040  *   The scoreboard isn't as necessary to the revised algorithm, but I kept it as a handy way to return the matched extension.
1041  *   The first complete match ends the traversal, which should make this version of the pattern matcher faster
1042  *   the previous. The same goes for "CANMATCH" or "MATCHMORE"; the first such match ends the traversal. In both
1043  *   these cases, the reason we can stop immediately, is because the first pattern match found will be the "best"
1044  *   according to the sort criteria.
1045  *   Hope the limit on stack depth won't be a problem... this routine should
1046  *   be pretty lean as far a stack usage goes. Any non-match terminates the recursion down a branch.
1047  *
1048  *   In the above example, with the number "3077549999" as the pattern, the traversor could match extensions a, b and d.  All are
1049  *   of length 10; they have total specificities of  24580, 10246, and 25090, respectively, not that this matters
1050  *   at all. (b) wins purely because the first character "3" is much more specific (lower specificity) than "N". I have
1051  *   left the specificity totals in the code as an artifact; at some point, I will strip it out.
1052  *
1053  *   Just how much time this algorithm might save over a plain linear traversal over all possible patterns is unknown,
1054  *   because it's a function of how many extensions are stored in a context. With thousands of extensions, the speedup
1055  *   can be very noticeable. The new matching algorithm can run several hundreds of times faster, if not a thousand or
1056  *   more times faster in extreme cases.
1057  *
1058  *   MatchCID patterns are also supported, and stored in the tree just as the extension pattern is. Thus, you
1059  *   can have patterns in your CID field as well.
1060  *
1061  * */
1062
1063
1064 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)
1065 {
1066         /* if this extension is marked as deleted, then skip this -- if it never shows
1067            on the scoreboard, it will never be found, nor will halt the traversal. */
1068         if (deleted)
1069                 return;
1070         board->total_specificity = spec;
1071         board->total_length = length;
1072         board->exten = exten;
1073         board->last_char = last;
1074         board->node = node;
1075 #ifdef NEED_DEBUG_HERE
1076         ast_log(LOG_NOTICE,"Scoreboarding (LONGER) %s, len=%d, score=%d\n", exten->exten, length, spec);
1077 #endif
1078 }
1079
1080 #ifdef NEED_DEBUG
1081 static void log_match_char_tree(struct match_char *node, char *prefix)
1082 {
1083         char extenstr[40];
1084         struct ast_str *my_prefix = ast_str_alloca(1024);
1085
1086         extenstr[0] = '\0';
1087
1088         if (node && node->exten)
1089                 snprintf(extenstr, sizeof(extenstr), "(%p)", node->exten);
1090
1091         if (strlen(node->x) > 1) {
1092                 ast_debug(1, "%s[%s]:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y':'N',
1093                         node->deleted? 'D':'-', node->specificity, node->exten? "EXTEN:":"",
1094                         node->exten ? node->exten->exten : "", extenstr);
1095         } else {
1096                 ast_debug(1, "%s%s:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y':'N',
1097                         node->deleted? 'D':'-', node->specificity, node->exten? "EXTEN:":"",
1098                         node->exten ? node->exten->exten : "", extenstr);
1099         }
1100
1101         ast_str_set(&my_prefix, 0, "%s+       ", prefix);
1102
1103         if (node->next_char)
1104                 log_match_char_tree(node->next_char, ast_str_buffer(my_prefix));
1105
1106         if (node->alt_char)
1107                 log_match_char_tree(node->alt_char, prefix);
1108 }
1109 #endif
1110
1111 static void cli_match_char_tree(struct match_char *node, char *prefix, int fd)
1112 {
1113         char extenstr[40];
1114         struct ast_str *my_prefix = ast_str_alloca(1024);
1115
1116         extenstr[0] = '\0';
1117
1118         if (node->exten) {
1119                 snprintf(extenstr, sizeof(extenstr), "(%p)", node->exten);
1120         }
1121
1122         if (strlen(node->x) > 1) {
1123                 ast_cli(fd, "%s[%s]:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y' : 'N',
1124                         node->deleted ? 'D' : '-', node->specificity, node->exten? "EXTEN:" : "",
1125                         node->exten ? node->exten->name : "", extenstr);
1126         } else {
1127                 ast_cli(fd, "%s%s:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y' : 'N',
1128                         node->deleted ? 'D' : '-', node->specificity, node->exten? "EXTEN:" : "",
1129                         node->exten ? node->exten->name : "", extenstr);
1130         }
1131
1132         ast_str_set(&my_prefix, 0, "%s+       ", prefix);
1133
1134         if (node->next_char)
1135                 cli_match_char_tree(node->next_char, ast_str_buffer(my_prefix), fd);
1136
1137         if (node->alt_char)
1138                 cli_match_char_tree(node->alt_char, prefix, fd);
1139 }
1140
1141 static struct ast_exten *get_canmatch_exten(struct match_char *node)
1142 {
1143         /* find the exten at the end of the rope */
1144         struct match_char *node2 = node;
1145
1146         for (node2 = node; node2; node2 = node2->next_char) {
1147                 if (node2->exten) {
1148 #ifdef NEED_DEBUG_HERE
1149                         ast_log(LOG_NOTICE,"CanMatch_exten returns exten %s(%p)\n", node2->exten->exten, node2->exten);
1150 #endif
1151                         return node2->exten;
1152                 }
1153         }
1154 #ifdef NEED_DEBUG_HERE
1155         ast_log(LOG_NOTICE,"CanMatch_exten returns NULL, match_char=%s\n", node->x);
1156 #endif
1157         return 0;
1158 }
1159
1160 static struct ast_exten *trie_find_next_match(struct match_char *node)
1161 {
1162         struct match_char *m3;
1163         struct match_char *m4;
1164         struct ast_exten *e3;
1165
1166         if (node && node->x[0] == '.' && !node->x[1]) { /* dot and ! will ALWAYS be next match in a matchmore */
1167                 return node->exten;
1168         }
1169
1170         if (node && node->x[0] == '!' && !node->x[1]) {
1171                 return node->exten;
1172         }
1173
1174         if (!node || !node->next_char) {
1175                 return NULL;
1176         }
1177
1178         m3 = node->next_char;
1179
1180         if (m3->exten) {
1181                 return m3->exten;
1182         }
1183         for (m4 = m3->alt_char; m4; m4 = m4->alt_char) {
1184                 if (m4->exten) {
1185                         return m4->exten;
1186                 }
1187         }
1188         for (m4 = m3; m4; m4 = m4->alt_char) {
1189                 e3 = trie_find_next_match(m3);
1190                 if (e3) {
1191                         return e3;
1192                 }
1193         }
1194
1195         return NULL;
1196 }
1197
1198 #ifdef DEBUG_THIS
1199 static char *action2str(enum ext_match_t action)
1200 {
1201         switch (action) {
1202         case E_MATCH:
1203                 return "MATCH";
1204         case E_CANMATCH:
1205                 return "CANMATCH";
1206         case E_MATCHMORE:
1207                 return "MATCHMORE";
1208         case E_FINDLABEL:
1209                 return "FINDLABEL";
1210         case E_SPAWN:
1211                 return "SPAWN";
1212         default:
1213                 return "?ACTION?";
1214         }
1215 }
1216
1217 #endif
1218
1219 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)
1220 {
1221         struct match_char *p; /* note minimal stack storage requirements */
1222         struct ast_exten pattern = { .label = label };
1223 #ifdef DEBUG_THIS
1224         if (tree)
1225                 ast_log(LOG_NOTICE,"new_find_extension called with %s on (sub)tree %s action=%s\n", str, tree->x, action2str(action));
1226         else
1227                 ast_log(LOG_NOTICE,"new_find_extension called with %s on (sub)tree NULL action=%s\n", str, action2str(action));
1228 #endif
1229         for (p = tree; p; p = p->alt_char) {
1230                 if (p->is_pattern) {
1231                         if (p->x[0] == 'N') {
1232                                 if (p->x[1] == 0 && *str >= '2' && *str <= '9' ) {
1233 #define NEW_MATCHER_CHK_MATCH          \
1234                                         if (p->exten && !(*(str + 1))) { /* if a shorter pattern matches along the way, might as well report it */             \
1235                                                 if (action == E_MATCH || action == E_SPAWN || action == E_FINDLABEL) { /* if in CANMATCH/MATCHMORE, don't let matches get in the way */   \
1236                                                         update_scoreboard(score, length + 1, spec + p->specificity, p->exten, 0, callerid, p->deleted, p);                 \
1237                                                         if (!p->deleted) {                                                                                           \
1238                                                                 if (action == E_FINDLABEL) {                                                                             \
1239                                                                         if (ast_hashtab_lookup(score->exten->peer_label_table, &pattern)) {                                  \
1240                                                                                 ast_debug(4, "Found label in preferred extension\n");                                            \
1241                                                                                 return;                                                                                          \
1242                                                                         }                                                                                                    \
1243                                                                 } else {                                                                                                 \
1244                                                                         ast_debug(4, "returning an exact match-- first found-- %s\n", p->exten->name);                       \
1245                                                                         return; /* the first match, by definition, will be the best, because of the sorted tree */           \
1246                                                                 }                                                                                                        \
1247                                                         }                                                                                                            \
1248                                                 }                                                                                                                \
1249                                         }
1250
1251 #define NEW_MATCHER_RECURSE                \
1252                                         if (p->next_char && (*(str + 1) || (p->next_char->x[0] == '/' && p->next_char->x[1] == 0)                 \
1253                                                        || p->next_char->x[0] == '!')) {                                          \
1254                                                 if (*(str + 1) || p->next_char->x[0] == '!') {                                                         \
1255                                                         new_find_extension(str + 1, score, p->next_char, length + 1, spec + p->specificity, callerid, label, action); \
1256                                                         if (score->exten)  {                                                                             \
1257                                                         ast_debug(4 ,"returning an exact match-- %s\n", score->exten->name);                         \
1258                                                                 return; /* the first match is all we need */                                                 \
1259                                                         }                                                                                                                                                \
1260                                                 } else {                                                                                             \
1261                                                         new_find_extension("/", score, p->next_char, length + 1, spec + p->specificity, callerid, label, action);        \
1262                                                         if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {      \
1263                                                         ast_debug(4,"returning a (can/more) match--- %s\n", score->exten ? score->exten->name :      \
1264                                                "NULL");                                                                        \
1265                                                                 return; /* the first match is all we need */                                                 \
1266                                                         }                                                                                                                                                \
1267                                                 }                                                                                                    \
1268                                         } else if ((p->next_char || action == E_CANMATCH) && !*(str + 1)) {                                                                  \
1269                                                 score->canmatch = 1;                                                                                 \
1270                                                 score->canmatch_exten = get_canmatch_exten(p);                                                       \
1271                                                 if (action == E_CANMATCH || action == E_MATCHMORE) {                                                 \
1272                                                 ast_debug(4, "returning a canmatch/matchmore--- str=%s\n", str);                                  \
1273                                                         return;                                                                                          \
1274                                                 }                                                                                                                                                    \
1275                                         }
1276
1277                                         NEW_MATCHER_CHK_MATCH;
1278                                         NEW_MATCHER_RECURSE;
1279                                 }
1280                         } else if (p->x[0] == 'Z') {
1281                                 if (p->x[1] == 0 && *str >= '1' && *str <= '9' ) {
1282                                         NEW_MATCHER_CHK_MATCH;
1283                                         NEW_MATCHER_RECURSE;
1284                                 }
1285                         } else if (p->x[0] == 'X') {
1286                                 if (p->x[1] == 0 && *str >= '0' && *str <= '9' ) {
1287                                         NEW_MATCHER_CHK_MATCH;
1288                                         NEW_MATCHER_RECURSE;
1289                                 }
1290                         } else if (p->x[0] == '.' && p->x[1] == 0) {
1291                                 /* how many chars will the . match against? */
1292                                 int i = 0;
1293                                 const char *str2 = str;
1294                                 while (*str2 && *str2 != '/') {
1295                                         str2++;
1296                                         i++;
1297                                 }
1298                                 if (p->exten && *str2 != '/') {
1299                                         update_scoreboard(score, length + i, spec + (i * p->specificity), p->exten, '.', callerid, p->deleted, p);
1300                                         if (score->exten) {
1301                                                 ast_debug(4, "return because scoreboard has a match with '/'--- %s\n",
1302                                                         score->exten->name);
1303                                                 return; /* the first match is all we need */
1304                                         }
1305                                 }
1306                                 if (p->next_char && p->next_char->x[0] == '/' && p->next_char->x[1] == 0) {
1307                                         new_find_extension("/", score, p->next_char, length + i, spec+(p->specificity*i), callerid, label, action);
1308                                         if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
1309                                                 ast_debug(4, "return because scoreboard has exact match OR "
1310                                                         "CANMATCH/MATCHMORE & canmatch set--- %s\n",
1311                                                         score->exten ? score->exten->name : "NULL");
1312                                                 return; /* the first match is all we need */
1313                                         }
1314                                 }
1315                         } else if (p->x[0] == '!' && p->x[1] == 0) {
1316                                 /* how many chars will the . match against? */
1317                                 int i = 1;
1318                                 const char *str2 = str;
1319                                 while (*str2 && *str2 != '/') {
1320                                         str2++;
1321                                         i++;
1322                                 }
1323                                 if (p->exten && *str2 != '/') {
1324                                         update_scoreboard(score, length + 1, spec + (p->specificity * i), p->exten, '!', callerid, p->deleted, p);
1325                                         if (score->exten) {
1326                                                 ast_debug(4, "return because scoreboard has a '!' match--- %s\n",
1327                                                         score->exten->name);
1328                                                 return; /* the first match is all we need */
1329                                         }
1330                                 }
1331                                 if (p->next_char && p->next_char->x[0] == '/' && p->next_char->x[1] == 0) {
1332                                         new_find_extension("/", score, p->next_char, length + i, spec + (p->specificity * i), callerid, label, action);
1333                                         if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
1334                                                 ast_debug(4, "return because scoreboard has exact match OR "
1335                                                         "CANMATCH/MATCHMORE & canmatch set with '/' and '!'--- %s\n",
1336                                                         score->exten ? score->exten->name : "NULL");
1337                                                 return; /* the first match is all we need */
1338                                         }
1339                                 }
1340                         } else if (p->x[0] == '/' && p->x[1] == 0) {
1341                                 /* the pattern in the tree includes the cid match! */
1342                                 if (p->next_char && callerid && *callerid) {
1343                                         new_find_extension(callerid, score, p->next_char, length + 1, spec, callerid, label, action);
1344                                         if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
1345                                                 ast_debug(4, "return because scoreboard has exact match OR "
1346                                                         "CANMATCH/MATCHMORE & canmatch set with '/'--- %s\n",
1347                                                         score->exten ? score->exten->name : "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->name, e1->name);
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->name, e1->name);
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 static int ext_fluff_count(const char *exten)
2134 {
2135         int fluff = 0;
2136
2137         if (*exten != '_') {
2138                 /* not a pattern, simple check. */
2139                 while (*exten) {
2140                         if (*exten == '-') {
2141                                 fluff++;
2142                         }
2143                         exten++;
2144                 }
2145
2146                 return fluff;
2147         }
2148
2149         /* do pattern check */
2150         while (*exten) {
2151                 if (*exten == '-') {
2152                         fluff++;
2153                 } else if (*exten == '[') {
2154                         /* skip set, dashes here matter. */
2155                         exten = strchr(exten, ']');
2156
2157                         if (!exten) {
2158                                 /* we'll end up warning about this later, don't spam logs */
2159                                 return fluff;
2160                         }
2161                 }
2162                 exten++;
2163         }
2164
2165         return fluff;
2166 }
2167
2168 int ast_extension_cmp(const char *a, const char *b)
2169 {
2170         int cmp;
2171
2172         cmp = ext_cmp(a, b);
2173         if (cmp < 0) {
2174                 return -1;
2175         }
2176         if (cmp > 0) {
2177                 return 1;
2178         }
2179         return 0;
2180 }
2181
2182 /*!
2183  * \internal
2184  * \brief used ast_extension_{match|close}
2185  * mode is as follows:
2186  *      E_MATCH         success only on exact match
2187  *      E_MATCHMORE     success only on partial match (i.e. leftover digits in pattern)
2188  *      E_CANMATCH      either of the above.
2189  * \retval 0 on no-match
2190  * \retval 1 on match
2191  * \retval 2 on early match.
2192  */
2193
2194 static int _extension_match_core(const char *pattern, const char *data, enum ext_match_t mode)
2195 {
2196         mode &= E_MATCH_MASK;   /* only consider the relevant bits */
2197
2198 #ifdef NEED_DEBUG_HERE
2199         ast_log(LOG_NOTICE,"match core: pat: '%s', dat: '%s', mode=%d\n", pattern, data, (int)mode);
2200 #endif
2201
2202         if (pattern[0] != '_') { /* not a pattern, try exact or partial match */
2203                 int lp = ext_cmp_exten_strlen(pattern);
2204                 int ld = ext_cmp_exten_strlen(data);
2205
2206                 if (lp < ld) {          /* pattern too short, cannot match */
2207 #ifdef NEED_DEBUG_HERE
2208                         ast_log(LOG_NOTICE,"return (0) - pattern too short, cannot match\n");
2209 #endif
2210                         return 0;
2211                 }
2212                 /* depending on the mode, accept full or partial match or both */
2213                 if (mode == E_MATCH) {
2214 #ifdef NEED_DEBUG_HERE
2215                         ast_log(LOG_NOTICE,"return (!ext_cmp_exten(%s,%s) when mode== E_MATCH)\n", pattern, data);
2216 #endif
2217                         return !ext_cmp_exten(pattern, data); /* 1 on match, 0 on fail */
2218                 }
2219                 if (ld == 0 || !ext_cmp_exten_partial(pattern, data)) { /* partial or full match */
2220 #ifdef NEED_DEBUG_HERE
2221                         ast_log(LOG_NOTICE,"return (mode(%d) == E_MATCHMORE ? lp(%d) > ld(%d) : 1)\n", mode, lp, ld);
2222 #endif
2223                         return (mode == E_MATCHMORE) ? lp > ld : 1; /* XXX should consider '!' and '/' ? */
2224                 } else {
2225 #ifdef NEED_DEBUG_HERE
2226                         ast_log(LOG_NOTICE,"return (0) when ld(%d) > 0 && pattern(%s) != data(%s)\n", ld, pattern, data);
2227 #endif
2228                         return 0;
2229                 }
2230         }
2231         if (mode == E_MATCH && data[0] == '_') {
2232                 /*
2233                  * XXX It is bad design that we don't know if we should be
2234                  * comparing data and pattern as patterns or comparing data if
2235                  * it conforms to pattern when the function is called.  First,
2236                  * assume they are both patterns.  If they don't match then try
2237                  * to see if data conforms to the given pattern.
2238                  *
2239                  * note: if this test is left out, then _x. will not match _x. !!!
2240                  */
2241 #ifdef NEED_DEBUG_HERE
2242                 ast_log(LOG_NOTICE, "Comparing as patterns first. pattern:%s data:%s\n", pattern, data);
2243 #endif
2244                 if (!ext_cmp_pattern(pattern + 1, data + 1)) {
2245 #ifdef NEED_DEBUG_HERE
2246                         ast_log(LOG_NOTICE,"return (1) - pattern matches pattern\n");
2247 #endif
2248                         return 1;
2249                 }
2250         }
2251
2252         ++pattern; /* skip leading _ */
2253         /*
2254          * XXX below we stop at '/' which is a separator for the CID info. However we should
2255          * not store '/' in the pattern at all. When we insure it, we can remove the checks.
2256          */
2257         for (;;) {
2258                 const char *end;
2259
2260                 /* Ignore '-' chars as eye candy fluff. */
2261                 while (*data == '-') {
2262                         ++data;
2263                 }
2264                 while (*pattern == '-') {
2265                         ++pattern;
2266                 }
2267                 if (!*data || !*pattern || *pattern == '/') {
2268                         break;
2269                 }
2270
2271                 switch (*pattern) {
2272                 case '[':       /* a range */
2273                         ++pattern;
2274                         end = strchr(pattern, ']'); /* XXX should deal with escapes ? */
2275                         if (!end) {
2276                                 ast_log(LOG_WARNING, "Wrong usage of [] in the extension\n");
2277                                 return 0;       /* unconditional failure */
2278                         }
2279                         if (pattern == end) {
2280                                 /* Ignore empty character sets. */
2281                                 ++pattern;
2282                                 continue;
2283                         }
2284                         for (; pattern < end; ++pattern) {
2285                                 if (pattern+2 < end && pattern[1] == '-') { /* this is a range */
2286                                         if (*data >= pattern[0] && *data <= pattern[2])
2287                                                 break;  /* match found */
2288                                         else {
2289                                                 pattern += 2; /* skip a total of 3 chars */
2290                                                 continue;
2291                                         }
2292                                 } else if (*data == pattern[0])
2293                                         break;  /* match found */
2294                         }
2295                         if (pattern >= end) {
2296 #ifdef NEED_DEBUG_HERE
2297                                 ast_log(LOG_NOTICE,"return (0) when pattern>=end\n");
2298 #endif
2299                                 return 0;
2300                         }
2301                         pattern = end;  /* skip and continue */
2302                         break;
2303                 case 'n':
2304                 case 'N':
2305                         if (*data < '2' || *data > '9') {
2306 #ifdef NEED_DEBUG_HERE
2307                                 ast_log(LOG_NOTICE,"return (0) N is not matched\n");
2308 #endif
2309                                 return 0;
2310                         }
2311                         break;
2312                 case 'x':
2313                 case 'X':
2314                         if (*data < '0' || *data > '9') {
2315 #ifdef NEED_DEBUG_HERE
2316                                 ast_log(LOG_NOTICE,"return (0) X is not matched\n");
2317 #endif
2318                                 return 0;
2319                         }
2320                         break;
2321                 case 'z':
2322                 case 'Z':
2323                         if (*data < '1' || *data > '9') {
2324 #ifdef NEED_DEBUG_HERE
2325                                 ast_log(LOG_NOTICE,"return (0) Z is not matched\n");
2326 #endif
2327                                 return 0;
2328                         }
2329                         break;
2330                 case '.':       /* Must match, even with more digits */
2331 #ifdef NEED_DEBUG_HERE
2332                         ast_log(LOG_NOTICE, "return (1) when '.' is matched\n");
2333 #endif
2334                         return 1;
2335                 case '!':       /* Early match */
2336 #ifdef NEED_DEBUG_HERE
2337                         ast_log(LOG_NOTICE, "return (2) when '!' is matched\n");
2338 #endif
2339                         return 2;
2340                 default:
2341                         if (*data != *pattern) {
2342 #ifdef NEED_DEBUG_HERE
2343                                 ast_log(LOG_NOTICE, "return (0) when *data(%c) != *pattern(%c)\n", *data, *pattern);
2344 #endif
2345                                 return 0;
2346                         }
2347                         break;
2348                 }
2349                 ++data;
2350                 ++pattern;
2351         }
2352         if (*data)                      /* data longer than pattern, no match */ {
2353 #ifdef NEED_DEBUG_HERE
2354                 ast_log(LOG_NOTICE, "return (0) when data longer than pattern\n");
2355 #endif
2356                 return 0;
2357         }
2358
2359         /*
2360          * match so far, but ran off the end of data.
2361          * Depending on what is next, determine match or not.
2362          */
2363         if (*pattern == '\0' || *pattern == '/') {      /* exact match */
2364 #ifdef NEED_DEBUG_HERE
2365                 ast_log(LOG_NOTICE, "at end, return (%d) in 'exact match'\n", (mode==E_MATCHMORE) ? 0 : 1);
2366 #endif
2367                 return (mode == E_MATCHMORE) ? 0 : 1;   /* this is a failure for E_MATCHMORE */
2368         } else if (*pattern == '!')     {               /* early match */
2369 #ifdef NEED_DEBUG_HERE
2370                 ast_log(LOG_NOTICE, "at end, return (2) when '!' is matched\n");
2371 #endif
2372                 return 2;
2373         } else {                                                /* partial match */
2374 #ifdef NEED_DEBUG_HERE
2375                 ast_log(LOG_NOTICE, "at end, return (%d) which deps on E_MATCH\n", (mode == E_MATCH) ? 0 : 1);
2376 #endif
2377                 return (mode == E_MATCH) ? 0 : 1;       /* this is a failure for E_MATCH */
2378         }
2379 }
2380
2381 /*
2382  * Wrapper around _extension_match_core() to do performance measurement
2383  * using the profiling code.
2384  */
2385 static int extension_match_core(const char *pattern, const char *data, enum ext_match_t mode)
2386 {
2387         int i;
2388         static int prof_id = -2;        /* marker for 'unallocated' id */
2389         if (prof_id == -2) {
2390                 prof_id = ast_add_profile("ext_match", 0);
2391         }
2392         ast_mark(prof_id, 1);
2393         i = _extension_match_core(ast_strlen_zero(pattern) ? "" : pattern, ast_strlen_zero(data) ? "" : data, mode);
2394         ast_mark(prof_id, 0);
2395         return i;
2396 }
2397
2398 int ast_extension_match(const char *pattern, const char *data)
2399 {
2400         return extension_match_core(pattern, data, E_MATCH);
2401 }
2402
2403 int ast_extension_close(const char *pattern, const char *data, int needmore)
2404 {
2405         if (needmore != E_MATCHMORE && needmore != E_CANMATCH)
2406                 ast_log(LOG_WARNING, "invalid argument %d\n", needmore);
2407         return extension_match_core(pattern, data, needmore);
2408 }
2409
2410 /* This structure must remain in sync with ast_context for proper hashtab matching */
2411 struct fake_context /* this struct is purely for matching in the hashtab */
2412 {
2413         ast_rwlock_t lock;
2414         struct ast_exten *root;
2415         struct ast_hashtab *root_table;
2416         struct match_char *pattern_tree;
2417         struct ast_context *next;
2418         struct ast_includes includes;
2419         struct ast_ignorepats ignorepats;
2420         struct ast_sws alts;
2421         const char *registrar;
2422         int refcount;
2423         int autohints;
2424         ast_mutex_t macrolock;
2425         char name[256];
2426 };
2427
2428 struct ast_context *ast_context_find(const char *name)
2429 {
2430         struct ast_context *tmp;
2431         struct fake_context item;
2432
2433         if (!name) {
2434                 return NULL;
2435         }
2436         ast_rdlock_contexts();
2437         if (contexts_table) {
2438                 ast_copy_string(item.name, name, sizeof(item.name));
2439                 tmp = ast_hashtab_lookup(contexts_table, &item);
2440         } else {
2441                 tmp = NULL;
2442                 while ((tmp = ast_walk_contexts(tmp))) {
2443                         if (!strcasecmp(name, tmp->name)) {
2444                                 break;
2445                         }
2446                 }
2447         }
2448         ast_unlock_contexts();
2449         return tmp;
2450 }
2451
2452 #define STATUS_NO_CONTEXT       1
2453 #define STATUS_NO_EXTENSION     2
2454 #define STATUS_NO_PRIORITY      3
2455 #define STATUS_NO_LABEL         4
2456 #define STATUS_SUCCESS          5
2457
2458 static int matchcid(const char *cidpattern, const char *callerid)
2459 {
2460         /* If the Caller*ID pattern is empty, then we're matching NO Caller*ID, so
2461            failing to get a number should count as a match, otherwise not */
2462
2463         if (ast_strlen_zero(callerid)) {
2464                 return ast_strlen_zero(cidpattern) ? 1 : 0;
2465         }
2466
2467         return ast_extension_match(cidpattern, callerid);
2468 }
2469
2470 struct ast_exten *pbx_find_extension(struct ast_channel *chan,
2471         struct ast_context *bypass, struct pbx_find_info *q,
2472         const char *context, const char *exten, int priority,
2473         const char *label, const char *callerid, enum ext_match_t action)
2474 {
2475         int x, res;
2476         struct ast_context *tmp = NULL;
2477         struct ast_exten *e = NULL, *eroot = NULL;
2478         struct ast_exten pattern = {NULL, };
2479         struct scoreboard score = {0, };
2480         struct ast_str *tmpdata = NULL;
2481         int idx;
2482
2483         pattern.label = label;
2484         pattern.priority = priority;
2485 #ifdef NEED_DEBUG_HERE
2486         ast_log(LOG_NOTICE, "Looking for cont/ext/prio/label/action = %s/%s/%d/%s/%d\n", context, exten, priority, label, (int) action);
2487 #endif
2488
2489         /* Initialize status if appropriate */
2490         if (q->stacklen == 0) {
2491                 q->status = STATUS_NO_CONTEXT;
2492                 q->swo = NULL;
2493                 q->data = NULL;
2494                 q->foundcontext = NULL;
2495         } else if (q->stacklen >= AST_PBX_MAX_STACK) {
2496                 ast_log(LOG_WARNING, "Maximum PBX stack exceeded\n");
2497                 return NULL;
2498         }
2499
2500         /* Check first to see if we've already been checked */
2501         for (x = 0; x < q->stacklen; x++) {
2502                 if (!strcasecmp(q->incstack[x], context))
2503                         return NULL;
2504         }
2505
2506         if (bypass) { /* bypass means we only look there */
2507                 tmp = bypass;
2508         } else {      /* look in contexts */
2509                 tmp = find_context(context);
2510                 if (!tmp) {
2511                         return NULL;
2512                 }
2513         }
2514
2515         if (q->status < STATUS_NO_EXTENSION)
2516                 q->status = STATUS_NO_EXTENSION;
2517
2518         /* Do a search for matching extension */
2519
2520         eroot = NULL;
2521         score.total_specificity = 0;
2522         score.exten = 0;
2523         score.total_length = 0;
2524         if (!tmp->pattern_tree && tmp->root_table) {
2525                 create_match_char_tree(tmp);
2526 #ifdef NEED_DEBUG
2527                 ast_debug(1, "Tree Created in context %s:\n", context);
2528                 log_match_char_tree(tmp->pattern_tree," ");
2529 #endif
2530         }
2531 #ifdef NEED_DEBUG
2532         ast_log(LOG_NOTICE, "The Trie we are searching in:\n");
2533         log_match_char_tree(tmp->pattern_tree, "::  ");
2534 #endif
2535
2536         do {
2537                 if (!ast_strlen_zero(overrideswitch)) {
2538                         char *osw = ast_strdupa(overrideswitch), *name;
2539                         struct ast_switch *asw;
2540                         ast_switch_f *aswf = NULL;
2541                         char *datap;
2542                         int eval = 0;
2543
2544                         name = strsep(&osw, "/");
2545                         asw = pbx_findswitch(name);
2546
2547                         if (!asw) {
2548                                 ast_log(LOG_WARNING, "No such switch '%s'\n", name);
2549                                 break;
2550                         }
2551
2552                         if (osw && strchr(osw, '$')) {
2553                                 eval = 1;
2554                         }
2555
2556                         if (eval && !(tmpdata = ast_str_thread_get(&switch_data, 512))) {
2557                                 ast_log(LOG_WARNING, "Can't evaluate overrideswitch?!\n");
2558                                 break;
2559                         } else if (eval) {
2560                                 /* Substitute variables now */
2561                                 pbx_substitute_variables_helper(chan, osw, ast_str_buffer(tmpdata), ast_str_size(tmpdata));
2562                                 datap = ast_str_buffer(tmpdata);
2563                         } else {
2564                                 datap = osw;
2565                         }
2566
2567                         /* equivalent of extension_match_core() at the switch level */
2568                         if (action == E_CANMATCH)
2569                                 aswf = asw->canmatch;
2570                         else if (action == E_MATCHMORE)
2571                                 aswf = asw->matchmore;
2572                         else /* action == E_MATCH */
2573                                 aswf = asw->exists;
2574                         if (!aswf) {
2575                                 res = 0;
2576                         } else {
2577                                 if (chan) {
2578                                         ast_autoservice_start(chan);
2579                                 }
2580                                 res = aswf(chan, context, exten, priority, callerid, datap);
2581                                 if (chan) {
2582                                         ast_autoservice_stop(chan);
2583                                 }
2584                         }
2585                         if (res) {      /* Got a match */
2586                                 q->swo = asw;
2587                                 q->data = datap;
2588                                 q->foundcontext = context;
2589                                 /* XXX keep status = STATUS_NO_CONTEXT ? */
2590                                 return NULL;
2591                         }
2592                 }
2593         } while (0);
2594
2595         if (extenpatternmatchnew) {
2596                 new_find_extension(exten, &score, tmp->pattern_tree, 0, 0, callerid, label, action);
2597                 eroot = score.exten;
2598
2599                 if (score.last_char == '!' && action == E_MATCHMORE) {
2600                         /* We match an extension ending in '!'.
2601                          * The decision in this case is final and is NULL (no match).
2602                          */
2603 #ifdef NEED_DEBUG_HERE
2604                         ast_log(LOG_NOTICE,"Returning MATCHMORE NULL with exclamation point.\n");
2605 #endif
2606                         return NULL;
2607                 }
2608
2609                 if (!eroot && (action == E_CANMATCH || action == E_MATCHMORE) && score.canmatch_exten) {
2610                         q->status = STATUS_SUCCESS;
2611 #ifdef NEED_DEBUG_HERE
2612                         ast_log(LOG_NOTICE,"Returning CANMATCH exten %s\n", score.canmatch_exten->exten);
2613 #endif
2614                         return score.canmatch_exten;
2615                 }
2616
2617                 if ((action == E_MATCHMORE || action == E_CANMATCH)  && eroot) {
2618                         if (score.node) {
2619                                 struct ast_exten *z = trie_find_next_match(score.node);
2620                                 if (z) {
2621 #ifdef NEED_DEBUG_HERE
2622                                         ast_log(LOG_NOTICE,"Returning CANMATCH/MATCHMORE next_match exten %s\n", z->exten);
2623 #endif
2624                                 } else {
2625                                         if (score.canmatch_exten) {
2626 #ifdef NEED_DEBUG_HERE
2627                                                 ast_log(LOG_NOTICE,"Returning CANMATCH/MATCHMORE canmatchmatch exten %s(%p)\n", score.canmatch_exten->exten, score.canmatch_exten);
2628 #endif
2629                                                 return score.canmatch_exten;
2630                                         } else {
2631 #ifdef NEED_DEBUG_HERE
2632                                                 ast_log(LOG_NOTICE,"Returning CANMATCH/MATCHMORE next_match exten NULL\n");
2633 #endif
2634                                         }
2635                                 }
2636                                 return z;
2637                         }
2638 #ifdef NEED_DEBUG_HERE
2639                         ast_log(LOG_NOTICE, "Returning CANMATCH/MATCHMORE NULL (no next_match)\n");
2640 #endif
2641                         return NULL;  /* according to the code, complete matches are null matches in MATCHMORE mode */
2642                 }
2643
2644                 if (eroot) {
2645                         /* found entry, now look for the right priority */
2646                         if (q->status < STATUS_NO_PRIORITY)
2647                                 q->status = STATUS_NO_PRIORITY;
2648                         e = NULL;
2649                         if (action == E_FINDLABEL && label ) {
2650                                 if (q->status < STATUS_NO_LABEL)
2651                                         q->status = STATUS_NO_LABEL;
2652                                 e = ast_hashtab_lookup(eroot->peer_label_table, &pattern);
2653                         } else {
2654                                 e = ast_hashtab_lookup(eroot->peer_table, &pattern);
2655                         }
2656                         if (e) {        /* found a valid match */
2657                                 q->status = STATUS_SUCCESS;
2658                                 q->foundcontext = context;
2659 #ifdef NEED_DEBUG_HERE
2660                                 ast_log(LOG_NOTICE,"Returning complete match of exten %s\n", e->exten);
2661 #endif
2662                                 return e;
2663                         }
2664                 }
2665         } else {   /* the old/current default exten pattern match algorithm */
2666
2667                 /* scan the list trying to match extension and CID */
2668                 eroot = NULL;
2669                 while ( (eroot = ast_walk_context_extensions(tmp, eroot)) ) {
2670                         int match = extension_match_core(eroot->exten, exten, action);
2671                         /* 0 on fail, 1 on match, 2 on earlymatch */
2672
2673                         if (!match || (eroot->matchcid && !matchcid(eroot->cidmatch, callerid)))
2674                                 continue;       /* keep trying */
2675                         if (match == 2 && action == E_MATCHMORE) {
2676                                 /* We match an extension ending in '!'.
2677                                  * The decision in this case is final and is NULL (no match).
2678                                  */
2679                                 return NULL;
2680                         }
2681                         /* found entry, now look for the right priority */
2682                         if (q->status < STATUS_NO_PRIORITY)
2683                                 q->status = STATUS_NO_PRIORITY;
2684                         e = NULL;
2685                         if (action == E_FINDLABEL && label ) {
2686                                 if (q->status < STATUS_NO_LABEL)
2687                                         q->status = STATUS_NO_LABEL;
2688                                 e = ast_hashtab_lookup(eroot->peer_label_table, &pattern);
2689                         } else {
2690                                 e = ast_hashtab_lookup(eroot->peer_table, &pattern);
2691                         }
2692                         if (e) {        /* found a valid match */
2693                                 q->status = STATUS_SUCCESS;
2694                                 q->foundcontext = context;
2695                                 return e;
2696                         }
2697                 }
2698         }
2699
2700         /* Check alternative switches */
2701         for (idx = 0; idx < ast_context_switches_count(tmp); idx++) {
2702                 const struct ast_sw *sw = ast_context_switches_get(tmp, idx);
2703                 struct ast_switch *asw = pbx_findswitch(ast_get_switch_name(sw));
2704                 ast_switch_f *aswf = NULL;
2705                 const char *datap;
2706
2707                 if (!asw) {
2708                         ast_log(LOG_WARNING, "No such switch '%s'\n", ast_get_switch_name(sw));
2709                         continue;
2710                 }
2711
2712                 /* Substitute variables now */
2713                 if (ast_get_switch_eval(sw)) {
2714                         if (!(tmpdata = ast_str_thread_get(&switch_data, 512))) {
2715                                 ast_log(LOG_WARNING, "Can't evaluate switch?!\n");
2716                                 continue;
2717                         }
2718                         pbx_substitute_variables_helper(chan, ast_get_switch_data(sw),
2719                                 ast_str_buffer(tmpdata), ast_str_size(tmpdata));
2720                         datap = ast_str_buffer(tmpdata);
2721                 } else {
2722                         datap = ast_get_switch_data(sw);
2723                 }
2724
2725                 /* equivalent of extension_match_core() at the switch level */
2726                 if (action == E_CANMATCH)
2727                         aswf = asw->canmatch;
2728                 else if (action == E_MATCHMORE)
2729                         aswf = asw->matchmore;
2730                 else /* action == E_MATCH */
2731                         aswf = asw->exists;
2732                 if (!aswf)
2733                         res = 0;
2734                 else {
2735                         if (chan)
2736                                 ast_autoservice_start(chan);
2737                         res = aswf(chan, context, exten, priority, callerid, datap);
2738                         if (chan)
2739                                 ast_autoservice_stop(chan);
2740                 }
2741                 if (res) {      /* Got a match */
2742                         q->swo = asw;
2743                         q->data = datap;
2744                         q->foundcontext = context;
2745                         /* XXX keep status = STATUS_NO_CONTEXT ? */
2746                         return NULL;
2747                 }
2748         }
2749         q->incstack[q->stacklen++] = tmp->name; /* Setup the stack */
2750         /* Now try any includes we have in this context */
2751         for (idx = 0; idx < ast_context_includes_count(tmp); idx++) {
2752                 const struct ast_include *i = ast_context_includes_get(tmp, idx);
2753
2754                 if (include_valid(i)) {
2755                         if ((e = pbx_find_extension(chan, bypass, q, include_rname(i), exten, priority, label, callerid, action))) {
2756 #ifdef NEED_DEBUG_HERE
2757                                 ast_log(LOG_NOTICE,"Returning recursive match of %s\n", e->exten);
2758 #endif
2759                                 return e;
2760                         }
2761                         if (q->swo)
2762                                 return NULL;
2763                 }
2764         }
2765         return NULL;
2766 }
2767
2768 static void exception_store_free(void *data)
2769 {
2770         struct pbx_exception *exception = data;
2771         ast_string_field_free_memory(exception);
2772         ast_free(exception);
2773 }
2774
2775 static const struct ast_datastore_info exception_store_info = {
2776         .type = "EXCEPTION",
2777         .destroy = exception_store_free,
2778 };
2779
2780 /*!
2781  * \internal
2782  * \brief Set the PBX to execute the exception extension.
2783  *
2784  * \param chan Channel to raise the exception on.
2785  * \param reason Reason exception is raised.
2786  * \param priority Dialplan priority to set.
2787  *
2788  * \retval 0 on success.
2789  * \retval -1 on error.
2790  */
2791 int raise_exception(struct ast_channel *chan, const char *reason, int priority)
2792 {
2793         struct ast_datastore *ds = ast_channel_datastore_find(chan, &exception_store_info, NULL);
2794         struct pbx_exception *exception = NULL;
2795
2796         if (!ds) {
2797                 ds = ast_datastore_alloc(&exception_store_info, NULL);
2798                 if (!ds)
2799                         return -1;
2800                 if (!(exception = ast_calloc_with_stringfields(1, struct pbx_exception, 128))) {
2801                         ast_datastore_free(ds);
2802                         return -1;
2803                 }
2804                 ds->data = exception;
2805                 ast_channel_datastore_add(chan, ds);
2806         } else
2807                 exception = ds->data;
2808
2809         ast_string_field_set(exception, reason, reason);
2810         ast_string_field_set(exception, context, ast_channel_context(chan));
2811         ast_string_field_set(exception, exten, ast_channel_exten(chan));
2812         exception->priority = ast_channel_priority(chan);
2813         set_ext_pri(chan, "e", priority);
2814         return 0;
2815 }
2816
2817 static int acf_exception_read(struct ast_channel *chan, const char *name, char *data, char *buf, size_t buflen)
2818 {
2819         struct ast_datastore *ds = ast_channel_datastore_find(chan, &exception_store_info, NULL);
2820         struct pbx_exception *exception = NULL;
2821         if (!ds || !ds->data)
2822                 return -1;
2823         exception = ds->data;
2824         if (!strcasecmp(data, "REASON"))
2825                 ast_copy_string(buf, exception->reason, buflen);
2826         else if (!strcasecmp(data, "CONTEXT"))
2827                 ast_copy_string(buf, exception->context, buflen);
2828         else if (!strncasecmp(data, "EXTEN", 5))
2829                 ast_copy_string(buf, exception->exten, buflen);
2830         else if (!strcasecmp(data, "PRIORITY"))
2831                 snprintf(buf, buflen, "%d", exception->priority);
2832         else
2833                 return -1;
2834         return 0;
2835 }
2836
2837 static struct ast_custom_function exception_function = {
2838         .name = "EXCEPTION",
2839         .read = acf_exception_read,
2840 };
2841
2842 /*!
2843  * \brief The return value depends on the action:
2844  *
2845  * E_MATCH, E_CANMATCH, E_MATCHMORE require a real match,
2846  *      and return 0 on failure, -1 on match;
2847  * E_FINDLABEL maps the label to a priority, and returns
2848  *      the priority on success, ... XXX
2849  * E_SPAWN, spawn an application,
2850  *
2851  * \retval 0 on success.
2852  * \retval  -1 on failure.
2853  *
2854  * \note The channel is auto-serviced in this function, because doing an extension
2855  * match may block for a long time.  For example, if the lookup has to use a network
2856  * dialplan switch, such as DUNDi or IAX2, it may take a while.  However, the channel
2857  * auto-service code will queue up any important signalling frames to be processed
2858  * after this is done.
2859  */
2860 static int pbx_extension_helper(struct ast_channel *c, struct ast_context *con,
2861   const char *context, const char *exten, int priority,
2862   const char *label, const char *callerid, enum ext_match_t action, int *found, int combined_find_spawn)
2863 {
2864         struct ast_exten *e;
2865         struct ast_app *app;
2866         char *substitute = NULL;
2867         struct pbx_find_info q = { .stacklen = 0 }; /* the rest is reset in pbx_find_extension */
2868         char passdata[EXT_DATA_SIZE];
2869         int matching_action = (action == E_MATCH || action == E_CANMATCH || action == E_MATCHMORE);
2870
2871         ast_rdlock_contexts();
2872         if (found)
2873                 *found = 0;
2874
2875         e = pbx_find_extension(c, con, &q, context, exten, priority, label, callerid, action);
2876         if (e) {
2877                 if (found)
2878                         *found = 1;
2879                 if (matching_action) {
2880                         ast_unlock_contexts();
2881                         return -1;      /* success, we found it */
2882                 } else if (action == E_FINDLABEL) { /* map the label to a priority */
2883                         int res = e->priority;
2884
2885                         ast_unlock_contexts();
2886
2887                         /* the priority we were looking for */
2888                         return res;
2889                 } else {        /* spawn */
2890                         if (!e->cached_app)
2891                                 e->cached_app = pbx_findapp(e->app);
2892                         app = e->cached_app;
2893                         if (ast_strlen_zero(e->data)) {
2894                                 *passdata = '\0';
2895                         } else {
2896                                 const char *tmp;
2897                                 if ((!(tmp = strchr(e->data, '$'))) || (!strstr(tmp, "${") && !strstr(tmp, "$["))) {
2898                                         /* no variables to substitute, copy on through */
2899                                         ast_copy_string(passdata, e->data, sizeof(passdata));
2900                                 } else {
2901                                         /* save e->data on stack for later processing after lock released */
2902                                         substitute = ast_strdupa(e->data);
2903                                 }
2904                         }
2905                         ast_unlock_contexts();
2906                         if (!app) {
2907                                 ast_log(LOG_WARNING, "No application '%s' for extension (%s, %s, %d)\n", e->app, context, exten, priority);
2908                                 return -1;
2909                         }
2910                         if (ast_channel_context(c) != context)
2911                                 ast_channel_context_set(c, context);
2912                         if (ast_channel_exten(c) != exten)
2913                                 ast_channel_exten_set(c, exten);
2914                         ast_channel_priority_set(c, priority);
2915                         if (substitute) {
2916                                 pbx_substitute_variables_helper(c, substitute, passdata, sizeof(passdata)-1);
2917                         }
2918                         ast_debug(1, "Launching '%s'\n", app_name(app));
2919                         if (VERBOSITY_ATLEAST(3)) {
2920                                 ast_verb(3, "Executing [%s@%s:%d] " COLORIZE_FMT "(\"" COLORIZE_FMT "\", \"" COLORIZE_FMT "\") %s\n",
2921                                         exten, context, priority,
2922                                         COLORIZE(COLOR_BRCYAN, 0, app_name(app)),
2923                                         COLORIZE(COLOR_BRMAGENTA, 0, ast_channel_name(c)),
2924                                         COLORIZE(COLOR_BRMAGENTA, 0, passdata),
2925                                         "in new stack");
2926                         }
2927                         return pbx_exec(c, app, passdata);      /* 0 on success, -1 on failure */
2928                 }
2929         } else if (q.swo) {     /* not found here, but in another switch */
2930                 if (found)
2931                         *found = 1;
2932                 ast_unlock_contexts();
2933                 if (matching_action) {
2934                         return -1;
2935                 } else {
2936                         if (!q.swo->exec) {
2937                                 ast_log(LOG_WARNING, "No execution engine for switch %s\n", q.swo->name);
2938                                 return -1;
2939                         }
2940                         return q.swo->exec(c, q.foundcontext ? q.foundcontext : context, exten, priority, callerid, q.data);
2941                 }
2942         } else {        /* not found anywhere, see what happened */
2943                 ast_unlock_contexts();
2944                 /* Using S_OR here because Solaris doesn't like NULL being passed to ast_log */
2945                 switch (q.status) {
2946                 case STATUS_NO_CONTEXT:
2947                         if (!matching_action && !combined_find_spawn)
2948                                 ast_log(LOG_NOTICE, "Cannot find extension context '%s'\n", S_OR(context, ""));
2949                         break;
2950                 case STATUS_NO_EXTENSION:
2951                         if (!matching_action && !combined_find_spawn)
2952                                 ast_log(LOG_NOTICE, "Cannot find extension '%s' in context '%s'\n", exten, S_OR(context, ""));
2953                         break;
2954                 case STATUS_NO_PRIORITY:
2955                         if (!matching_action && !combined_find_spawn)
2956                                 ast_log(LOG_NOTICE, "No such priority %d in extension '%s' in context '%s'\n", priority, exten, S_OR(context, ""));
2957                         break;
2958                 case STATUS_NO_LABEL:
2959                         if (context && !combined_find_spawn)
2960                                 ast_log(LOG_NOTICE, "No such label '%s' in extension '%s' in context '%s'\n", label, exten, S_OR(context, ""));
2961                         break;
2962                 default:
2963                         ast_debug(1, "Shouldn't happen!\n");
2964                 }
2965
2966                 return (matching_action) ? 0 : -1;
2967         }
2968 }
2969
2970 /*! \brief Find hint for given extension in context */
2971 static struct ast_exten *ast_hint_extension_nolock(struct ast_channel *c, const char *context, const char *exten)
2972 {
2973         struct pbx_find_info q = { .stacklen = 0 }; /* the rest is set in pbx_find_context */
2974         return pbx_find_extension(c, NULL, &q, context, exten, PRIORITY_HINT, NULL, "", E_MATCH);