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