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