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