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