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