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