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