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