make datastore creation and destruction a generic API since it is not really channel...
[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         },
673
674         { "MSet", pbx_builtin_setvar_multiple,
675         "Set channel variable(s) or function value(s)",
676         "  MSet(name1=value1,name2=value2,...)\n"
677         "This function can be used to set the value of channel variables or dialplan\n"
678         "functions. When setting variables, if the variable name is prefixed with _,\n"
679         "the variable will be inherited into channels created from the current\n"
680         "channel. If the variable name is prefixed with __, the variable will be\n"
681         "inherited into channels created from the current channel and all children\n"
682         "channels.\n\n"
683         "MSet behaves in a similar fashion to the way Set worked in 1.2/1.4 and is thus\n"
684         "prone to doing things that you may not expect.  Avoid its use if possible.\n"
685         },
686
687         { "SetAMAFlags", pbx_builtin_setamaflags,
688         "Set the AMA Flags",
689         "  SetAMAFlags([flag]): This application will set the channel's AMA Flags for\n"
690         "  billing purposes.\n"
691         },
692
693         { "Wait", pbx_builtin_wait,
694         "Waits for some time",
695         "  Wait(seconds): This application waits for a specified number of seconds.\n"
696         "Then, dialplan execution will continue at the next priority.\n"
697         "  Note that the seconds can be passed with fractions of a second. For example,\n"
698         "'1.5' will ask the application to wait for 1.5 seconds.\n"
699         },
700
701         { "WaitExten", pbx_builtin_waitexten,
702         "Waits for an extension to be entered",
703         "  WaitExten([seconds][,options]): This application waits for the user to enter\n"
704         "a new extension for a specified number of seconds.\n"
705         "  Note that the seconds can be passed with fractions of a second. For example,\n"
706         "'1.5' will ask the application to wait for 1.5 seconds.\n"
707         "  Options:\n"
708         "    m[(x)] - Provide music on hold to the caller while waiting for an extension.\n"
709         "               Optionally, specify the class for music on hold within parenthesis.\n"
710         "See Also: Playback(application), Background(application).\n"
711         },
712
713 };
714
715 static struct ast_context *contexts;
716 static struct ast_hashtab *contexts_table = NULL;
717
718 AST_RWLOCK_DEFINE_STATIC(conlock);              /*!< Lock for the ast_context list */
719
720 static AST_RWLIST_HEAD_STATIC(apps, ast_app);
721
722 static AST_RWLIST_HEAD_STATIC(switches, ast_switch);
723
724 static int stateid = 1;
725 /* WARNING:
726    When holding this list's lock, do _not_ do anything that will cause conlock
727    to be taken, unless you _already_ hold it. The ast_merge_contexts_and_delete
728    function will take the locks in conlock/hints order, so any other
729    paths that require both locks must also take them in that order.
730 */
731 static AST_RWLIST_HEAD_STATIC(hints, ast_hint);
732
733 static AST_LIST_HEAD_NOLOCK_STATIC(statecbs, ast_state_cb);
734
735 #ifdef CONTEXT_DEBUG
736
737 /* these routines are provided for doing run-time checks
738    on the extension structures, in case you are having
739    problems, this routine might help you localize where
740    the problem is occurring. It's kinda like a debug memory
741    allocator's arena checker... It'll eat up your cpu cycles!
742    but you'll see, if you call it in the right places,
743    right where your problems began...
744 */
745
746 /* you can break on the check_contexts_trouble()
747 routine in your debugger to stop at the moment
748 there's a problem */
749 void check_contexts_trouble(void);
750
751 void check_contexts_trouble(void)
752 {
753         int x = 1;
754         x = 2;
755 }
756
757 static struct ast_context *find_context_locked(const char *context);
758 int check_contexts(char *, int);
759
760 int check_contexts(char *file, int line )
761 {
762         struct ast_hashtab_iter *t1;
763         struct ast_context *c1, *c2;
764         int found = 0;
765         struct ast_exten *e1, *e2, *e3;
766         struct ast_exten ex;
767         
768         /* try to find inconsistencies */
769         /* is every context in the context table in the context list and vice-versa ? */
770         
771         if (!contexts_table) {
772                 ast_log(LOG_NOTICE,"Called from: %s:%d: No contexts_table!\n", file, line);
773                 usleep(500000);
774         }
775
776         t1 = ast_hashtab_start_traversal(contexts_table);
777         while( (c1 = ast_hashtab_next(t1))) {
778                 for(c2=contexts;c2;c2=c2->next) {
779                         if (!strcmp(c1->name, c2->name)) {
780                                 found = 1;
781                                 break;
782                         }
783                 }
784                 if (!found) {
785                         ast_log(LOG_NOTICE,"Called from: %s:%d: Could not find the %s context in the linked list\n", file, line, c1->name);
786                         check_contexts_trouble();
787                 }
788         }
789         ast_hashtab_end_traversal(t1);
790         for(c2=contexts;c2;c2=c2->next) {
791                 c1 = find_context_locked(c2->name);
792                 if (!c1) {
793                         ast_log(LOG_NOTICE,"Called from: %s:%d: Could not find the %s context in the hashtab\n", file, line, c2->name);
794                         check_contexts_trouble();
795                 } else
796                         ast_unlock_contexts();
797         }
798
799         /* loop thru all contexts, and verify the exten structure compares to the 
800            hashtab structure */
801         for(c2=contexts;c2;c2=c2->next) {
802                 c1 = find_context_locked(c2->name);
803                 if (c1)
804                 {
805
806                         ast_unlock_contexts();
807
808                         /* is every entry in the root list also in the root_table? */
809                         for(e1 = c1->root; e1; e1=e1->next)
810                         {
811                                 char dummy_name[1024];
812                                 ex.exten = dummy_name;
813                                 ex.matchcid = e1->matchcid;
814                                 ex.cidmatch = e1->cidmatch;
815                                 ast_copy_string(dummy_name, e1->exten, sizeof(dummy_name));
816                                 e2 = ast_hashtab_lookup(c1->root_table, &ex);
817                                 if (!e2) {
818                                         if (e1->matchcid) {
819                                                 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 );
820                                         } else {
821                                                 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 );
822                                         }
823                                         check_contexts_trouble();
824                                 }
825                         }
826                         
827                         /* is every entry in the root_table also in the root list? */ 
828                         if (!c2->root_table) {
829                                 if (c2->root) {
830                                         ast_log(LOG_NOTICE,"Called from: %s:%d: No c2->root_table for context %s!\n", file, line, c2->name);
831                                         usleep(500000);
832                                 }
833                         } else {
834                                 t1 = ast_hashtab_start_traversal(c2->root_table);
835                                 while( (e2 = ast_hashtab_next(t1)) ) {
836                                         for(e1=c2->root;e1;e1=e1->next) {
837                                                 if (!strcmp(e1->exten, e2->exten)) {
838                                                         found = 1;
839                                                         break;
840                                                 }
841                                         }
842                                         if (!found) {
843                                                 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);
844                                                 check_contexts_trouble();
845                                         }
846                                         
847                                 }
848                                 ast_hashtab_end_traversal(t1);
849                         }
850                 }
851                 /* is every priority reflected in the peer_table at the head of the list? */
852                 
853                 /* is every entry in the root list also in the root_table? */
854                 /* are the per-extension peer_tables in the right place? */
855
856                 for(e1 = c2->root; e1; e1 = e1->next) {
857                         
858                         for(e2=e1;e2;e2=e2->peer) {
859                                 ex.priority = e2->priority;
860                                 if (e2 != e1 && e2->peer_table) {
861                                         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 );
862                                         check_contexts_trouble();
863                                 }
864                                 
865                                 if (e2 != e1 && e2->peer_label_table) {
866                                         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 );
867                                         check_contexts_trouble();
868                                 }
869                                 
870                                 if (e2 == e1 && !e2->peer_table){
871                                         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 );
872                                         check_contexts_trouble();
873                                 }
874                                 
875                                 if (e2 == e1 && !e2->peer_label_table) {
876                                         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 );
877                                         check_contexts_trouble();
878                                 }
879                                 
880
881                                 e3 = ast_hashtab_lookup(e1->peer_table, &ex);
882                                 if (!e3) {
883                                         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 );
884                                         check_contexts_trouble();
885                                 }
886                         }
887                         
888                         if (!e1->peer_table){
889                                 ast_log(LOG_NOTICE,"Called from: %s:%d: No e1->peer_table!\n", file, line);
890                                 usleep(500000);
891                         }
892                         
893                         /* is every entry in the peer_table also in the peer list? */ 
894                         t1 = ast_hashtab_start_traversal(e1->peer_table);
895                         while( (e2 = ast_hashtab_next(t1)) ) {
896                                 for(e3=e1;e3;e3=e3->peer) {
897                                         if (e3->priority == e2->priority) {
898                                                 found = 1;
899                                                 break;
900                                         }
901                                 }
902                                 if (!found) {
903                                         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 );
904                                         check_contexts_trouble();
905                                 }
906                         }
907                         ast_hashtab_end_traversal(t1);
908                 }
909         }
910         return 0;
911 }
912 #endif
913
914 /*
915    \note This function is special. It saves the stack so that no matter
916    how many times it is called, it returns to the same place */
917 int pbx_exec(struct ast_channel *c,             /*!< Channel */
918              struct ast_app *app,               /*!< Application */
919              void *data)                        /*!< Data for execution */
920 {
921         int res;
922         struct ast_module_user *u = NULL;
923         const char *saved_c_appl;
924         const char *saved_c_data;
925
926         if (c->cdr && !ast_check_hangup(c))
927                 ast_cdr_setapp(c->cdr, app->name, data);
928
929         /* save channel values */
930         saved_c_appl= c->appl;
931         saved_c_data= c->data;
932
933         c->appl = app->name;
934         c->data = data;
935         if (app->module)
936                 u = __ast_module_user_add(app->module, c);
937         res = app->execute(c, S_OR(data, ""));
938         if (app->module && u)
939                 __ast_module_user_remove(app->module, u);
940         /* restore channel values */
941         c->appl = saved_c_appl;
942         c->data = saved_c_data;
943         return res;
944 }
945
946
947 /*! Go no deeper than this through includes (not counting loops) */
948 #define AST_PBX_MAX_STACK       128
949
950 /*! \brief Find application handle in linked list
951  */
952 struct ast_app *pbx_findapp(const char *app)
953 {
954         struct ast_app *tmp;
955
956         AST_RWLIST_RDLOCK(&apps);
957         AST_RWLIST_TRAVERSE(&apps, tmp, list) {
958                 if (!strcasecmp(tmp->name, app))
959                         break;
960         }
961         AST_RWLIST_UNLOCK(&apps);
962
963         return tmp;
964 }
965
966 static struct ast_switch *pbx_findswitch(const char *sw)
967 {
968         struct ast_switch *asw;
969
970         AST_RWLIST_RDLOCK(&switches);
971         AST_RWLIST_TRAVERSE(&switches, asw, list) {
972                 if (!strcasecmp(asw->name, sw))
973                         break;
974         }
975         AST_RWLIST_UNLOCK(&switches);
976
977         return asw;
978 }
979
980 static inline int include_valid(struct ast_include *i)
981 {
982         if (!i->hastime)
983                 return 1;
984
985         return ast_check_timing(&(i->timing));
986 }
987
988 static void pbx_destroy(struct ast_pbx *p)
989 {
990         ast_free(p);
991 }
992
993 /* form a tree that fully describes all the patterns in a context's extensions 
994  * in this tree, a "node" represents an individual character or character set
995  * meant to match the corresponding character in a dial string. The tree 
996  * consists of a series of match_char structs linked in a chain
997  * via the alt_char pointers. More than one pattern can share the same parts of the 
998  * tree as other extensions with the same pattern to that point. 
999  * My first attempt to duplicate the finding of the 'best' pattern was flawed in that
1000  * I misunderstood the general algorithm. I thought that the 'best' pattern
1001  * was the one with lowest total score. This was not true. Thus, if you have
1002  * patterns "1XXXXX" and "X11111", you would be tempted to say that "X11111" is
1003  * the "best" match because it has fewer X's, and is therefore more specific, 
1004  * but this is not how the old algorithm works. It sorts matching patterns
1005  * in a similar collating sequence as sorting alphabetic strings, from left to 
1006  * right. Thus, "1XXXXX" comes before "X11111", and would be the "better" match,
1007  * because "1" is more specific than "X".
1008  * So, to accomodate this philosophy, I sort the tree branches along the alt_char
1009  * line so they are lowest to highest in specificity numbers. This way, as soon
1010  * as we encounter our first complete match, we automatically have the "best" 
1011  * match and can stop the traversal immediately. Same for CANMATCH/MATCHMORE.
1012  * If anyone would like to resurrect the "wrong" pattern trie searching algorithm,
1013  * they are welcome to revert pbx to before 1 Apr 2008.
1014  * As an example, consider these 4 extensions:
1015  * (a) NXXNXXXXXX
1016  * (b) 307754XXXX 
1017  * (c) fax
1018  * (d) NXXXXXXXXX
1019  *
1020  * In the above, between (a) and (d), (a) is a more specific pattern than (d), and would win over
1021  * most numbers. For all numbers beginning with 307754, (b) should always win.
1022  *
1023  * These pattern should form a (sorted) tree that looks like this:
1024  *   { "3" }  --next-->  { "0" }  --next--> { "7" } --next--> { "7" } --next--> { "5" } ... blah ... --> { "X" exten_match: (b) }
1025  *      |
1026  *      |alt
1027  *      |
1028  *   { "f" }  --next-->  { "a" }  --next--> { "x"  exten_match: (c) }
1029  *   { "N" }  --next-->  { "X" }  --next--> { "X" } --next--> { "N" } --next--> { "X" } ... blah ... --> { "X" exten_match: (a) }
1030  *      |                                                        |
1031  *      |                                                        |alt
1032  *      |alt                                                     |
1033  *      |                                                     { "X" } --next--> { "X" } ... blah ... --> { "X" exten_match: (d) }
1034  *      |
1035  *     NULL
1036  *
1037  *   In the above, I could easily turn "N" into "23456789", but I think that a quick "if( *z >= '2' && *z <= '9' )" might take
1038  *   fewer CPU cycles than a call to index("23456789",*z), where *z is the char to match...
1039  *
1040  *   traversal is pretty simple: one routine merely traverses the alt list, and for each matching char in the pattern,  it calls itself
1041  *   on the corresponding next pointer, incrementing also the pointer of the string to be matched, and passing the total specificity and length.
1042  *   We pass a pointer to a scoreboard down through, also.
1043  *   The scoreboard isn't as necessary to the revised algorithm, but I kept it as a handy way to return the matched extension.
1044  *   The first complete match ends the traversal, which should make this version of the pattern matcher faster
1045  *   the previous. The same goes for "CANMATCH" or "MATCHMORE"; the first such match ends the traversal. In both
1046  *   these cases, the reason we can stop immediately, is because the first pattern match found will be the "best"
1047  *   according to the sort criteria.
1048  *   Hope the limit on stack depth won't be a problem... this routine should 
1049  *   be pretty lean as far a stack usage goes. Any non-match terminates the recursion down a branch.
1050  *
1051  *   In the above example, with the number "3077549999" as the pattern, the traversor could match extensions a, b and d.  All are
1052  *   of length 10; they have total specificities of  24580, 10246, and 25090, respectively, not that this matters
1053  *   at all. (b) wins purely because the first character "3" is much more specific (lower specificity) than "N". I have
1054  *   left the specificity totals in the code as an artifact; at some point, I will strip it out.
1055  *
1056  *   Just how much time this algorithm might save over a plain linear traversal over all possible patterns is unknown,
1057  *   because it's a function of how many extensions are stored in a context. With thousands of extensions, the speedup
1058  *   can be very noticeable. The new matching algorithm can run several hundreds of times faster, if not a thousand or
1059  *   more times faster in extreme cases.
1060  *
1061  *   MatchCID patterns are also supported, and stored in the tree just as the extension pattern is. Thus, you
1062  *   can have patterns in your CID field as well.
1063  *
1064  * */
1065
1066
1067 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)
1068 {
1069         /* if this extension is marked as deleted, then skip this -- if it never shows
1070            on the scoreboard, it will never be found, nor will halt the traversal. */
1071         if (deleted)
1072                 return;
1073         board->total_specificity = spec;
1074         board->total_length = length;
1075         board->exten = exten;
1076         board->last_char = last;
1077         board->node = node;
1078 #ifdef NEED_DEBUG_HERE
1079         ast_log(LOG_NOTICE,"Scoreboarding (LONGER) %s, len=%d, score=%d\n", exten->exten, length, spec);
1080 #endif
1081 }
1082
1083 void log_match_char_tree(struct match_char *node, char *prefix)
1084 {
1085         char extenstr[40];
1086         struct ast_str *my_prefix = ast_str_alloca(1024); 
1087
1088         extenstr[0] = '\0';
1089
1090         if (node && node->exten && node->exten)
1091                 snprintf(extenstr, sizeof(extenstr), "(%p)", node->exten);
1092         
1093         if (strlen(node->x) > 1) {
1094                 ast_debug(1, "%s[%s]:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y':'N', 
1095                         node->deleted? 'D':'-', node->specificity, node->exten? "EXTEN:":"", 
1096                         node->exten ? node->exten->exten : "", extenstr);
1097         } else {
1098                 ast_debug(1, "%s%s:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y':'N', 
1099                         node->deleted? 'D':'-', node->specificity, node->exten? "EXTEN:":"", 
1100                         node->exten ? node->exten->exten : "", extenstr);
1101         }
1102
1103         ast_str_set(&my_prefix, 0, "%s+       ", prefix);
1104
1105         if (node->next_char)
1106                 log_match_char_tree(node->next_char, my_prefix->str);
1107
1108         if (node->alt_char)
1109                 log_match_char_tree(node->alt_char, prefix);
1110 }
1111
1112 static void cli_match_char_tree(struct match_char *node, char *prefix, int fd)
1113 {
1114         char extenstr[40];
1115         struct ast_str *my_prefix = ast_str_alloca(1024);
1116         
1117         extenstr[0] = '\0';
1118
1119         if (node && node->exten && node->exten)
1120                 snprintf(extenstr, sizeof(extenstr), "(%p)", node->exten);
1121         
1122         if (strlen(node->x) > 1) {
1123                 ast_cli(fd, "%s[%s]:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y' : 'N', 
1124                         node->deleted ? 'D' : '-', node->specificity, node->exten? "EXTEN:" : "", 
1125                         node->exten ? node->exten->exten : "", extenstr);
1126         } else {
1127                 ast_cli(fd, "%s%s:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y' : 'N', 
1128                         node->deleted ? 'D' : '-', node->specificity, node->exten? "EXTEN:" : "", 
1129                         node->exten ? node->exten->exten : "", extenstr);
1130         }
1131
1132         ast_str_set(&my_prefix, 0, "%s+       ", prefix);
1133
1134         if (node->next_char)
1135                 cli_match_char_tree(node->next_char, my_prefix->str, fd);
1136
1137         if (node->alt_char)
1138                 cli_match_char_tree(node->alt_char, prefix, fd);
1139 }
1140
1141 static struct ast_exten *get_canmatch_exten(struct match_char *node)
1142 {
1143         /* find the exten at the end of the rope */
1144         struct match_char *node2 = node;
1145
1146         for (node2 = node; node2; node2 = node2->next_char) {
1147                 if (node2->exten) {
1148 #ifdef NEED_DEBUG_HERE
1149                         ast_log(LOG_NOTICE,"CanMatch_exten returns exten %s(%p)\n", node2->exten->exten, node2->exten);
1150 #endif
1151                         return node2->exten;
1152                 }
1153         }
1154 #ifdef NEED_DEBUG_HERE
1155         ast_log(LOG_NOTICE,"CanMatch_exten returns NULL, match_char=%s\n", node->x);
1156 #endif
1157         return 0;
1158 }
1159
1160 static struct ast_exten *trie_find_next_match(struct match_char *node)
1161 {
1162         struct match_char *m3;
1163         struct match_char *m4;
1164         struct ast_exten *e3;
1165         
1166         if (node && node->x[0] == '.' && !node->x[1]) /* dot and ! will ALWAYS be next match in a matchmore */
1167                 return node->exten;
1168         
1169         if (node && node->x[0] == '!' && !node->x[1])
1170                 return node->exten;
1171         
1172         if (!node || !node->next_char)
1173                 return NULL;
1174         
1175         m3 = node->next_char;
1176
1177         if (m3->exten)
1178                 return m3->exten;
1179         for(m4=m3->alt_char; m4; m4 = m4->alt_char) {
1180                 if (m4->exten)
1181                         return m4->exten;
1182         }
1183         for(m4=m3; m4; m4 = m4->alt_char) {
1184                 e3 = trie_find_next_match(m3);
1185                 if (e3)
1186                         return e3;
1187         }
1188         return NULL;
1189 }
1190
1191 #ifdef DEBUG_THIS
1192 static char *action2str(enum ext_match_t action)
1193 {
1194         switch(action)
1195         {
1196         case E_MATCH:
1197                 return "MATCH";
1198         case E_CANMATCH:
1199                 return "CANMATCH";
1200         case E_MATCHMORE:
1201                 return "MATCHMORE";
1202         case E_FINDLABEL:
1203                 return "FINDLABEL";
1204         case E_SPAWN:
1205                 return "SPAWN";
1206         default:
1207                 return "?ACTION?";
1208         }
1209 }
1210
1211 #endif
1212
1213 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)
1214 {
1215         struct match_char *p; /* note minimal stack storage requirements */
1216         struct ast_exten pattern = { .label = label };
1217 #ifdef DEBUG_THIS
1218         if (tree)
1219                 ast_log(LOG_NOTICE,"new_find_extension called with %s on (sub)tree %s action=%s\n", str, tree->x, action2str(action));
1220         else
1221                 ast_log(LOG_NOTICE,"new_find_extension called with %s on (sub)tree NULL action=%s\n", str, action2str(action));
1222 #endif
1223         for (p=tree; p; p=p->alt_char) {
1224                 if (p->x[0] == 'N') {
1225                         if (p->x[1] == 0 && *str >= '2' && *str <= '9' ) {
1226 #define NEW_MATCHER_CHK_MATCH          \
1227                                 if (p->exten && !(*(str+1))) { /* if a shorter pattern matches along the way, might as well report it */             \
1228                                         if (action == E_MATCH || action == E_SPAWN || action == E_FINDLABEL) { /* if in CANMATCH/MATCHMORE, don't let matches get in the way */   \
1229                                                 update_scoreboard(score, length+1, spec+p->specificity, p->exten,0,callerid, p->deleted, p);                 \
1230                                                 if (!p->deleted) {                                                                                           \
1231                                                         if (action == E_FINDLABEL) {                                                                             \
1232                                                                 if (ast_hashtab_lookup(score->exten->peer_label_table, &pattern)) {                                  \
1233                                                                         ast_debug(4, "Found label in preferred extension\n");                                            \
1234                                                                         return;                                                                                          \
1235                                                                 }                                                                                                    \
1236                                                         } else {                                                                                                 \
1237                                                                 ast_debug(4,"returning an exact match-- first found-- %s\n", p->exten->exten);                       \
1238                                                                 return; /* the first match, by definition, will be the best, because of the sorted tree */           \
1239                                                         }                                                                                                        \
1240                                                 }                                                                                                            \
1241                                         }                                                                                                                \
1242                                 }
1243                                 
1244 #define NEW_MATCHER_RECURSE                \
1245                                 if (p->next_char && ( *(str+1) || (p->next_char->x[0] == '/' && p->next_char->x[1] == 0)                 \
1246                                                || p->next_char->x[0] == '!')) {                                          \
1247                                         if (*(str+1) || p->next_char->x[0] == '!') {                                                         \
1248                                                 new_find_extension(str+1, score, p->next_char, length+1, spec+p->specificity, callerid, label, action); \
1249                                                 if (score->exten)  {                                                                             \
1250                                                 ast_debug(4,"returning an exact match-- %s\n", score->exten->exten);                         \
1251                                                         return; /* the first match is all we need */                                                 \
1252                                                 }                                                                                                                                                \
1253                                         } else {                                                                                             \
1254                                                 new_find_extension("/", score, p->next_char, length+1, spec+p->specificity, callerid, label, action);    \
1255                                                 if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {      \
1256                                                 ast_debug(4,"returning a (can/more) match--- %s\n", score->exten ? score->exten->exten :     \
1257                                        "NULL");                                                                        \
1258                                                         return; /* the first match is all we need */                                                 \
1259                                                 }                                                                                                                                                \
1260                                         }                                                                                                    \
1261                                 } else if (p->next_char && !*(str+1)) {                                                                  \
1262                                         score->canmatch = 1;                                                                                 \
1263                                         score->canmatch_exten = get_canmatch_exten(p);                                                       \
1264                                         if (action == E_CANMATCH || action == E_MATCHMORE) {                                                 \
1265                                         ast_debug(4,"returning a canmatch/matchmore--- str=%s\n", str);                                  \
1266                                                 return;                                                                                          \
1267                                         }                                                                                                                                                    \
1268                                 }
1269                                 
1270                                 NEW_MATCHER_CHK_MATCH;
1271                                 NEW_MATCHER_RECURSE;
1272                         }
1273                 } else if (p->x[0] == 'Z') {
1274                         if (p->x[1] == 0 && *str >= '1' && *str <= '9' ) {
1275                                 NEW_MATCHER_CHK_MATCH;
1276                                 NEW_MATCHER_RECURSE;
1277                         }
1278                 } else if (p->x[0] == 'X') { 
1279                         if (p->x[1] == 0 && *str >= '0' && *str <= '9' ) {
1280                                 NEW_MATCHER_CHK_MATCH;
1281                                 NEW_MATCHER_RECURSE;
1282                         }
1283                 } else if (p->x[0] == '.' && p->x[1] == 0) {
1284                         /* how many chars will the . match against? */
1285                         int i = 0;
1286                         const char *str2 = str;
1287                         while (*str2 && *str2 != '/') {
1288                                 str2++;
1289                                 i++;
1290                         }
1291                         if (p->exten && *str2 != '/') {
1292                                 update_scoreboard(score, length+i, spec+(i*p->specificity), p->exten, '.', callerid, p->deleted, p);
1293                                 if (score->exten) {
1294                                         ast_debug(4,"return because scoreboard has a match with '/'--- %s\n", score->exten->exten);
1295                                         return; /* the first match is all we need */
1296                                 }
1297                         }
1298                         if (p->next_char && p->next_char->x[0] == '/' && p->next_char->x[1] == 0) {
1299                                 new_find_extension("/", score, p->next_char, length+i, spec+(p->specificity*i), callerid, label, action);
1300                                 if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
1301                                         ast_debug(4,"return because scoreboard has exact match OR CANMATCH/MATCHMORE & canmatch set--- %s\n", score->exten ? score->exten->exten : "NULL");
1302                                         return; /* the first match is all we need */
1303                                 }
1304                         }
1305                 } else if (p->x[0] == '!' && p->x[1] == 0) {
1306                         /* how many chars will the . match against? */
1307                         int i = 1;
1308                         const char *str2 = str;
1309                         while (*str2 && *str2 != '/') {
1310                                 str2++;
1311                                 i++;
1312                         }
1313                         if (p->exten && *str2 != '/') {
1314                                 update_scoreboard(score, length+1, spec+(p->specificity*i), p->exten, '!', callerid, p->deleted, p);
1315                                 if (score->exten) {
1316                                         ast_debug(4,"return because scoreboard has a '!' match--- %s\n", score->exten->exten);
1317                                         return; /* the first match is all we need */
1318                                 }
1319                         }
1320                         if (p->next_char && p->next_char->x[0] == '/' && p->next_char->x[1] == 0) {
1321                                 new_find_extension("/", score, p->next_char, length+i, spec+(p->specificity*i), callerid, label, action);
1322                                 if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
1323                                         ast_debug(4,"return because scoreboard has exact match OR CANMATCH/MATCHMORE & canmatch set with '/' and '!'--- %s\n", score->exten ? score->exten->exten : "NULL");
1324                                         return; /* the first match is all we need */
1325                                 }
1326                         }
1327                 } else if (p->x[0] == '/' && p->x[1] == 0) {
1328                         /* the pattern in the tree includes the cid match! */
1329                         if (p->next_char && callerid && *callerid) {
1330                                 new_find_extension(callerid, score, p->next_char, length+1, spec, callerid, label, action);
1331                                 if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
1332                                         ast_debug(4,"return because scoreboard has exact match OR CANMATCH/MATCHMORE & canmatch set with '/'--- %s\n", score->exten ? score->exten->exten : "NULL");
1333                                         return; /* the first match is all we need */
1334                                 }
1335                         }
1336                 } else if (index(p->x, *str)) {
1337                         ast_debug(4, "Nothing strange about this match\n");
1338                         NEW_MATCHER_CHK_MATCH;
1339                         NEW_MATCHER_RECURSE;
1340                 }
1341         }
1342         ast_debug(4,"return at end of func\n");
1343 }
1344
1345 /* the algorithm for forming the extension pattern tree is also a bit simple; you 
1346  * traverse all the extensions in a context, and for each char of the extension,
1347  * you see if it exists in the tree; if it doesn't, you add it at the appropriate
1348  * spot. What more can I say? At the end of each exten, you cap it off by adding the
1349  * address of the extension involved. Duplicate patterns will be complained about.
1350  *
1351  * Ideally, this would be done for each context after it is created and fully 
1352  * filled. It could be done as a finishing step after extensions.conf or .ael is
1353  * loaded, or it could be done when the first search is encountered. It should only
1354  * have to be done once, until the next unload or reload.
1355  *
1356  * I guess forming this pattern tree would be analogous to compiling a regex. Except
1357  * that a regex only handles 1 pattern, really. This trie holds any number
1358  * of patterns. Well, really, it **could** be considered a single pattern,
1359  * where the "|" (or) operator is allowed, I guess, in a way, sort of...
1360  */
1361
1362 static struct match_char *already_in_tree(struct match_char *current, char *pat)
1363 {
1364         struct match_char *t;
1365
1366         if (!current)
1367                 return 0;
1368
1369         for (t = current; t; t = t->alt_char) {
1370                 if (!strcmp(pat, t->x)) /* uh, we may want to sort exploded [] contents to make matching easy */
1371                         return t;
1372         }
1373
1374         return 0;
1375 }
1376
1377 /* The first arg is the location of the tree ptr, or the 
1378    address of the next_char ptr in the node, so we can mess
1379    with it, if we need to insert at the beginning of the list */
1380
1381 static void insert_in_next_chars_alt_char_list(struct match_char **parent_ptr, struct match_char *node)
1382 {
1383         struct match_char *curr, *lcurr;
1384         
1385         /* insert node into the tree at "current", so the alt_char list from current is
1386            sorted in increasing value as you go to the leaves */
1387         if (!(*parent_ptr)) {
1388                 *parent_ptr = node;
1389         } else {
1390                 if ((*parent_ptr)->specificity > node->specificity){
1391                         /* insert at head */
1392                         node->alt_char = (*parent_ptr);
1393                         *parent_ptr = node;
1394                 } else {
1395                         lcurr = *parent_ptr;
1396                         for (curr=(*parent_ptr)->alt_char; curr; curr = curr->alt_char) {
1397                                 if (curr->specificity > node->specificity) {
1398                                         node->alt_char = curr;
1399                                         lcurr->alt_char = node;
1400                                         break;
1401                                 }
1402                                 lcurr = curr;
1403                         }
1404                         if (!curr)
1405                         {
1406                                 lcurr->alt_char = node;
1407                         }
1408                 }
1409         }
1410 }
1411
1412
1413
1414 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)
1415 {
1416         struct match_char *m;
1417         
1418         if (!(m = ast_calloc(1, sizeof(*m))))
1419                 return NULL;
1420
1421         if (!(m->x = ast_strdup(pattern))) {
1422                 ast_free(m);
1423                 return NULL;
1424         }
1425
1426         /* the specificity scores are the same as used in the old
1427            pattern matcher. */
1428         m->is_pattern = is_pattern;
1429         if (specificity == 1 && is_pattern && pattern[0] == 'N')
1430                 m->specificity = 0x0802;
1431         else if (specificity == 1 && is_pattern && pattern[0] == 'Z')
1432                 m->specificity = 0x0901;
1433         else if (specificity == 1 && is_pattern && pattern[0] == 'X')
1434                 m->specificity = 0x0a00;
1435         else if (specificity == 1 && is_pattern && pattern[0] == '.')
1436                 m->specificity = 0x10000;
1437         else if (specificity == 1 && is_pattern && pattern[0] == '!')
1438                 m->specificity = 0x20000;
1439         else
1440                 m->specificity = specificity;
1441         
1442         if (!con->pattern_tree) {
1443                 insert_in_next_chars_alt_char_list(&con->pattern_tree, m);
1444         } else {
1445                 if (already) { /* switch to the new regime (traversing vs appending)*/
1446                         insert_in_next_chars_alt_char_list(nextcharptr, m);
1447                 } else {
1448                         insert_in_next_chars_alt_char_list(&current->next_char, m);
1449                 }
1450         }
1451
1452         return m;
1453 }
1454
1455 static struct match_char *add_exten_to_pattern_tree(struct ast_context *con, struct ast_exten *e1, int findonly)
1456 {
1457         struct match_char *m1 = NULL, *m2 = NULL, **m0;
1458         int specif;
1459         int already;
1460         int pattern = 0;
1461         char buf[256];
1462         char extenbuf[512];
1463         char *s1 = extenbuf;
1464         int l1 = strlen(e1->exten) + strlen(e1->cidmatch) + 2;
1465         
1466
1467         strncpy(extenbuf,e1->exten,sizeof(extenbuf));
1468         if (e1->matchcid &&  l1 <= sizeof(extenbuf)) {
1469                 strcat(extenbuf,"/");
1470                 strcat(extenbuf,e1->cidmatch);
1471         } else if (l1 > sizeof(extenbuf)) {
1472                 ast_log(LOG_ERROR,"The pattern %s/%s is too big to deal with: it will be ignored! Disaster!\n", e1->exten, e1->cidmatch);
1473                 return 0;
1474         }
1475 #ifdef NEED_DEBUG
1476         ast_log(LOG_DEBUG,"Adding exten %s%c%s to tree\n", s1, e1->matchcid? '/':' ', e1->matchcid? e1->cidmatch : "");
1477 #endif
1478         m1 = con->pattern_tree; /* each pattern starts over at the root of the pattern tree */
1479         m0 = &con->pattern_tree;
1480         already = 1;
1481
1482         if ( *s1 == '_') {
1483                 pattern = 1;
1484                 s1++;
1485         }
1486         while( *s1 ) {
1487                 if (pattern && *s1 == '[' && *(s1-1) != '\\') {
1488                         char *s2 = buf;
1489                         buf[0] = 0;
1490                         s1++; /* get past the '[' */
1491                         while (*s1 != ']' && *(s1-1) != '\\' ) {
1492                                 if (*s1 == '\\') {
1493                                         if (*(s1+1) == ']') {
1494                                                 *s2++ = ']';
1495                                                 s1++;s1++;
1496                                         } else if (*(s1+1) == '\\') {
1497                                                 *s2++ = '\\';
1498                                                 s1++;s1++;
1499                                         } else if (*(s1+1) == '-') {
1500                                                 *s2++ = '-';
1501                                                 s1++; s1++;
1502                                         } else if (*(s1+1) == '[') {
1503                                                 *s2++ = '[';
1504                                                 s1++; s1++;
1505                                         }
1506                                 } else if (*s1 == '-') { /* remember to add some error checking to all this! */
1507                                         char s3 = *(s1-1);
1508                                         char s4 = *(s1+1);
1509                                         for (s3++; s3 <= s4; s3++) {
1510                                                 *s2++ = s3;
1511                                         }
1512                                         s1++; s1++;
1513                                 } else {
1514                                         *s2++ = *s1++;
1515                                 }
1516                         }
1517                         *s2 = 0; /* null terminate the exploded range */
1518                         /* sort the characters */
1519
1520                         specif = strlen(buf);
1521                         qsort(buf, specif, 1, compare_char);
1522                         specif <<= 8;
1523                         specif += buf[0];
1524                 } else {
1525                         
1526                         if (*s1 == '\\') {
1527                                 s1++;
1528                                 buf[0] = *s1;
1529                         } else {
1530                                 if (pattern) {
1531                                         if (*s1 == 'n') /* make sure n,x,z patterns are canonicalized to N,X,Z */
1532                                                 *s1 = 'N';
1533                                         else if (*s1 == 'x')
1534                                                 *s1 = 'X';
1535                                         else if (*s1 == 'z')
1536                                                 *s1 = 'Z';
1537                                 }
1538                                 buf[0] = *s1;
1539                         }
1540                         buf[1] = 0;
1541                         specif = 1;
1542                 }
1543                 m2 = 0;
1544                 if (already && (m2=already_in_tree(m1,buf)) && m2->next_char) {
1545                         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...
1546                                                                 a shorter pattern might win if the longer one doesn't match */
1547                                 m2->exten = e1;
1548                                 m2->deleted = 0;
1549                         }
1550                         m1 = m2->next_char; /* m1 points to the node to compare against */
1551                         m0 = &m2->next_char; /* m0 points to the ptr that points to m1 */
1552                 } else { /* not already OR not m2 OR nor m2->next_char */
1553                         if (m2) {
1554                                 if (findonly)
1555                                         return m2;
1556                                 m1 = m2; /* while m0 stays the same */
1557                         } else {
1558                                 if (findonly)
1559                                         return m1;
1560                                 m1 = add_pattern_node(con, m1, buf, pattern, already,specif, m0); /* m1 is the node just added */
1561                                 m0 = &m1->next_char;
1562                         }
1563                         
1564                         if (!(*(s1+1))) {
1565                                 m1->deleted = 0;
1566                                 m1->exten = e1;
1567                         }
1568                         
1569                         already = 0;
1570                 }
1571                 s1++; /* advance to next char */
1572         }
1573         return m1;
1574 }
1575
1576 static void create_match_char_tree(struct ast_context *con)
1577 {
1578         struct ast_hashtab_iter *t1;
1579         struct ast_exten *e1;
1580 #ifdef NEED_DEBUG
1581         int biggest_bucket, resizes, numobjs, numbucks;
1582         
1583         ast_log(LOG_DEBUG,"Creating Extension Trie for context %s\n", con->name);
1584         ast_hashtab_get_stats(con->root_table, &biggest_bucket, &resizes, &numobjs, &numbucks);
1585         ast_log(LOG_DEBUG,"This tree has %d objects in %d bucket lists, longest list=%d objects, and has resized %d times\n",
1586                         numobjs, numbucks, biggest_bucket, resizes);
1587 #endif
1588         t1 = ast_hashtab_start_traversal(con->root_table);
1589         while( (e1 = ast_hashtab_next(t1)) ) {
1590                 if (e1->exten)
1591                         add_exten_to_pattern_tree(con, e1, 0);
1592                 else
1593                         ast_log(LOG_ERROR,"Attempt to create extension with no extension name.\n");
1594         }
1595         ast_hashtab_end_traversal(t1);
1596 }
1597
1598 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! */
1599 {
1600         /* destroy all the alternates */
1601         if (pattern_tree->alt_char) {
1602                 destroy_pattern_tree(pattern_tree->alt_char);
1603                 pattern_tree->alt_char = 0;
1604         }
1605         /* destroy all the nexts */
1606         if (pattern_tree->next_char) {
1607                 destroy_pattern_tree(pattern_tree->next_char);
1608                 pattern_tree->next_char = 0;
1609         }
1610         pattern_tree->exten = 0; /* never hurts to make sure there's no pointers laying around */
1611         if (pattern_tree->x)
1612                 free(pattern_tree->x);
1613         free(pattern_tree);
1614 }
1615
1616 /*
1617  * Special characters used in patterns:
1618  *      '_'     underscore is the leading character of a pattern.
1619  *              In other position it is treated as a regular char.
1620  *      ' ' '-' space and '-' are separator and ignored.
1621  *      .       one or more of any character. Only allowed at the end of
1622  *              a pattern.
1623  *      !       zero or more of anything. Also impacts the result of CANMATCH
1624  *              and MATCHMORE. Only allowed at the end of a pattern.
1625  *              In the core routine, ! causes a match with a return code of 2.
1626  *              In turn, depending on the search mode: (XXX check if it is implemented)
1627  *              - E_MATCH retuns 1 (does match)
1628  *              - E_MATCHMORE returns 0 (no match)
1629  *              - E_CANMATCH returns 1 (does match)
1630  *
1631  *      /       should not appear as it is considered the separator of the CID info.
1632  *              XXX at the moment we may stop on this char.
1633  *
1634  *      X Z N   match ranges 0-9, 1-9, 2-9 respectively.
1635  *      [       denotes the start of a set of character. Everything inside
1636  *              is considered literally. We can have ranges a-d and individual
1637  *              characters. A '[' and '-' can be considered literally if they
1638  *              are just before ']'.
1639  *              XXX currently there is no way to specify ']' in a range, nor \ is
1640  *              considered specially.
1641  *
1642  * When we compare a pattern with a specific extension, all characters in the extension
1643  * itself are considered literally with the only exception of '-' which is considered
1644  * as a separator and thus ignored.
1645  * XXX do we want to consider space as a separator as well ?
1646  * XXX do we want to consider the separators in non-patterns as well ?
1647  */
1648
1649 /*!
1650  * \brief helper functions to sort extensions and patterns in the desired way,
1651  * so that more specific patterns appear first.
1652  *
1653  * ext_cmp1 compares individual characters (or sets of), returning
1654  * an int where bits 0-7 are the ASCII code of the first char in the set,
1655  * while bit 8-15 are the cardinality of the set minus 1.
1656  * This way more specific patterns (smaller cardinality) appear first.
1657  * Wildcards have a special value, so that we can directly compare them to
1658  * sets by subtracting the two values. In particular:
1659  *      0x000xx         one character, xx
1660  *      0x0yyxx         yy character set starting with xx
1661  *      0x10000         '.' (one or more of anything)
1662  *      0x20000         '!' (zero or more of anything)
1663  *      0x30000         NUL (end of string)
1664  *      0x40000         error in set.
1665  * The pointer to the string is advanced according to needs.
1666  * NOTES:
1667  *      1. the empty set is equivalent to NUL.
1668  *      2. given that a full set has always 0 as the first element,
1669  *         we could encode the special cases as 0xffXX where XX
1670  *         is 1, 2, 3, 4 as used above.
1671  */
1672 static int ext_cmp1(const char **p)
1673 {
1674         uint32_t chars[8];
1675         int c, cmin = 0xff, count = 0;
1676         const char *end;
1677
1678         /* load, sign extend and advance pointer until we find
1679          * a valid character.
1680          */
1681         while ( (c = *(*p)++) && (c == ' ' || c == '-') )
1682                 ;       /* ignore some characters */
1683
1684         /* always return unless we have a set of chars */
1685         switch (toupper(c)) {
1686         default:        /* ordinary character */
1687                 return 0x0000 | (c & 0xff);
1688
1689         case 'N':       /* 2..9 */
1690                 return 0x0700 | '2' ;
1691
1692         case 'X':       /* 0..9 */
1693                 return 0x0900 | '0';
1694
1695         case 'Z':       /* 1..9 */
1696                 return 0x0800 | '1';
1697
1698         case '.':       /* wildcard */
1699                 return 0x10000;
1700
1701         case '!':       /* earlymatch */
1702                 return 0x20000; /* less specific than NULL */
1703
1704         case '\0':      /* empty string */
1705                 *p = NULL;
1706                 return 0x30000;
1707
1708         case '[':       /* pattern */
1709                 break;
1710         }
1711         /* locate end of set */
1712         end = strchr(*p, ']');  
1713
1714         if (end == NULL) {
1715                 ast_log(LOG_WARNING, "Wrong usage of [] in the extension\n");
1716                 return 0x40000; /* XXX make this entry go last... */
1717         }
1718
1719         bzero(chars, sizeof(chars));    /* clear all chars in the set */
1720         for (; *p < end  ; (*p)++) {
1721                 unsigned char c1, c2;   /* first-last char in range */
1722                 c1 = (unsigned char)((*p)[0]);
1723                 if (*p + 2 < end && (*p)[1] == '-') { /* this is a range */
1724                         c2 = (unsigned char)((*p)[2]);
1725                         *p += 2;        /* skip a total of 3 chars */
1726                 } else                  /* individual character */
1727                         c2 = c1;
1728                 if (c1 < cmin)
1729                         cmin = c1;
1730                 for (; c1 <= c2; c1++) {
1731                         uint32_t mask = 1 << (c1 % 32);
1732                         if ( (chars[ c1 / 32 ] & mask) == 0)
1733                                 count += 0x100;
1734                         chars[ c1 / 32 ] |= mask;
1735                 }
1736         }
1737         (*p)++;
1738         return count == 0 ? 0x30000 : (count | cmin);
1739 }
1740
1741 /*!
1742  * \brief the full routine to compare extensions in rules.
1743  */
1744 static int ext_cmp(const char *a, const char *b)
1745 {
1746         /* make sure non-patterns come first.
1747          * If a is not a pattern, it either comes first or
1748          * we use strcmp to compare the strings.
1749          */
1750         int ret = 0;
1751
1752         if (a[0] != '_')
1753                 return (b[0] == '_') ? -1 : strcmp(a, b);
1754
1755         /* Now we know a is a pattern; if b is not, a comes first */
1756         if (b[0] != '_')
1757                 return 1;
1758 #if 0   /* old mode for ext matching */
1759         return strcmp(a, b);
1760 #endif
1761         /* ok we need full pattern sorting routine */
1762         while (!ret && a && b)
1763                 ret = ext_cmp1(&a) - ext_cmp1(&b);
1764         if (ret == 0)
1765                 return 0;
1766         else
1767                 return (ret > 0) ? 1 : -1;
1768 }
1769
1770 int ast_extension_cmp(const char *a, const char *b)
1771 {
1772         return ext_cmp(a, b);
1773 }
1774
1775 /*!
1776  * \internal
1777  * \brief used ast_extension_{match|close}
1778  * mode is as follows:
1779  *      E_MATCH         success only on exact match
1780  *      E_MATCHMORE     success only on partial match (i.e. leftover digits in pattern)
1781  *      E_CANMATCH      either of the above.
1782  * \retval 0 on no-match
1783  * \retval 1 on match
1784  * \retval 2 on early match.
1785  */
1786
1787 static int _extension_match_core(const char *pattern, const char *data, enum ext_match_t mode)
1788 {
1789         mode &= E_MATCH_MASK;   /* only consider the relevant bits */
1790         
1791 #ifdef NEED_DEBUG_HERE
1792         ast_log(LOG_NOTICE,"match core: pat: '%s', dat: '%s', mode=%d\n", pattern, data, (int)mode);
1793 #endif
1794         
1795         if ( (mode == E_MATCH) && (pattern[0] == '_') && (!strcasecmp(pattern,data)) ) { /* note: if this test is left out, then _x. will not match _x. !!! */
1796 #ifdef NEED_DEBUG_HERE
1797                 ast_log(LOG_NOTICE,"return (1) - pattern matches pattern\n");
1798 #endif
1799                 return 1;
1800         }
1801
1802         if (pattern[0] != '_') { /* not a pattern, try exact or partial match */
1803                 int ld = strlen(data), lp = strlen(pattern);
1804                 
1805                 if (lp < ld) {          /* pattern too short, cannot match */
1806 #ifdef NEED_DEBUG_HERE
1807                         ast_log(LOG_NOTICE,"return (0) - pattern too short, cannot match\n");
1808 #endif
1809                         return 0;
1810                 }
1811                 /* depending on the mode, accept full or partial match or both */
1812                 if (mode == E_MATCH) {
1813 #ifdef NEED_DEBUG_HERE
1814                         ast_log(LOG_NOTICE,"return (!strcmp(%s,%s) when mode== E_MATCH)\n", pattern, data);
1815 #endif
1816                         return !strcmp(pattern, data); /* 1 on match, 0 on fail */
1817                 } 
1818                 if (ld == 0 || !strncasecmp(pattern, data, ld)) { /* partial or full match */
1819 #ifdef NEED_DEBUG_HERE
1820                         ast_log(LOG_NOTICE,"return (mode(%d) == E_MATCHMORE ? lp(%d) > ld(%d) : 1)\n", mode, lp, ld);
1821 #endif
1822                         return (mode == E_MATCHMORE) ? lp > ld : 1; /* XXX should consider '!' and '/' ? */
1823                 } else {
1824 #ifdef NEED_DEBUG_HERE
1825                         ast_log(LOG_NOTICE,"return (0) when ld(%d) > 0 && pattern(%s) != data(%s)\n", ld, pattern, data);
1826 #endif
1827                         return 0;
1828                 }
1829         }
1830         pattern++; /* skip leading _ */
1831         /*
1832          * XXX below we stop at '/' which is a separator for the CID info. However we should
1833          * not store '/' in the pattern at all. When we insure it, we can remove the checks.
1834          */
1835         while (*data && *pattern && *pattern != '/') {
1836                 const char *end;
1837
1838                 if (*data == '-') { /* skip '-' in data (just a separator) */
1839                         data++;
1840                         continue;
1841                 }
1842                 switch (toupper(*pattern)) {
1843                 case '[':       /* a range */
1844                         end = strchr(pattern+1, ']'); /* XXX should deal with escapes ? */
1845                         if (end == NULL) {
1846                                 ast_log(LOG_WARNING, "Wrong usage of [] in the extension\n");
1847                                 return 0;       /* unconditional failure */
1848                         }
1849                         for (pattern++; pattern != end; pattern++) {
1850                                 if (pattern+2 < end && pattern[1] == '-') { /* this is a range */
1851                                         if (*data >= pattern[0] && *data <= pattern[2])
1852                                                 break;  /* match found */
1853                                         else {
1854                                                 pattern += 2; /* skip a total of 3 chars */
1855                                                 continue;
1856                                         }
1857                                 } else if (*data == pattern[0])
1858                                         break;  /* match found */
1859                         }
1860                         if (pattern == end) {
1861 #ifdef NEED_DEBUG_HERE
1862                                 ast_log(LOG_NOTICE,"return (0) when pattern==end\n");
1863 #endif
1864                                 return 0;
1865                         }
1866                         pattern = end;  /* skip and continue */
1867                         break;
1868                 case 'N':
1869                         if (*data < '2' || *data > '9') {
1870 #ifdef NEED_DEBUG_HERE
1871                                 ast_log(LOG_NOTICE,"return (0) N is matched\n");
1872 #endif
1873                                 return 0;
1874                         }
1875                         break;
1876                 case 'X':
1877                         if (*data < '0' || *data > '9') {
1878 #ifdef NEED_DEBUG_HERE
1879                                 ast_log(LOG_NOTICE,"return (0) X is matched\n");
1880 #endif
1881                                 return 0;
1882                         }
1883                         break;
1884                 case 'Z':
1885                         if (*data < '1' || *data > '9') {
1886 #ifdef NEED_DEBUG_HERE
1887                                 ast_log(LOG_NOTICE,"return (0) Z is matched\n");
1888 #endif
1889                                 return 0;
1890                         }
1891                         break;
1892                 case '.':       /* Must match, even with more digits */
1893 #ifdef NEED_DEBUG_HERE
1894                         ast_log(LOG_NOTICE,"return (1) when '.' is matched\n");
1895 #endif
1896                         return 1;
1897                 case '!':       /* Early match */
1898 #ifdef NEED_DEBUG_HERE
1899                         ast_log(LOG_NOTICE,"return (2) when '!' is matched\n");
1900 #endif
1901                         return 2;
1902                 case ' ':
1903                 case '-':       /* Ignore these in patterns */
1904                         data--; /* compensate the final data++ */
1905                         break;
1906                 default:
1907                         if (*data != *pattern) {
1908 #ifdef NEED_DEBUG_HERE
1909                                 ast_log(LOG_NOTICE,"return (0) when *data(%c) != *pattern(%c)\n", *data, *pattern);
1910 #endif
1911                                 return 0;
1912                         }
1913                         
1914                 }
1915                 data++;
1916                 pattern++;
1917         }
1918         if (*data)                      /* data longer than pattern, no match */ {
1919 #ifdef NEED_DEBUG_HERE
1920                 ast_log(LOG_NOTICE,"return (0) when data longer than pattern\n");
1921 #endif
1922                 return 0;
1923         }
1924         
1925         /*
1926          * match so far, but ran off the end of the data.
1927          * Depending on what is next, determine match or not.
1928          */
1929         if (*pattern == '\0' || *pattern == '/') {      /* exact match */
1930 #ifdef NEED_DEBUG_HERE
1931                 ast_log(LOG_NOTICE,"at end, return (%d) in 'exact match'\n", (mode==E_MATCHMORE) ? 0 : 1);
1932 #endif
1933                 return (mode == E_MATCHMORE) ? 0 : 1;   /* this is a failure for E_MATCHMORE */
1934         } else if (*pattern == '!')     {               /* early match */
1935 #ifdef NEED_DEBUG_HERE
1936                 ast_log(LOG_NOTICE,"at end, return (2) when '!' is matched\n");
1937 #endif
1938                 return 2;
1939         } else {                                                /* partial match */
1940 #ifdef NEED_DEBUG_HERE
1941                 ast_log(LOG_NOTICE,"at end, return (%d) which deps on E_MATCH\n", (mode == E_MATCH) ? 0 : 1);
1942 #endif
1943                 return (mode == E_MATCH) ? 0 : 1;       /* this is a failure for E_MATCH */
1944         }
1945 }
1946
1947 /*
1948  * Wrapper around _extension_match_core() to do performance measurement
1949  * using the profiling code.
1950  */
1951 static int extension_match_core(const char *pattern, const char *data, enum ext_match_t mode)
1952 {
1953         int i;
1954         static int prof_id = -2;        /* marker for 'unallocated' id */
1955         if (prof_id == -2)
1956                 prof_id = ast_add_profile("ext_match", 0);
1957         ast_mark(prof_id, 1);
1958         i = _extension_match_core(pattern, data, mode);
1959         ast_mark(prof_id, 0);
1960         return i;
1961 }
1962
1963 int ast_extension_match(const char *pattern, const char *data)
1964 {
1965         return extension_match_core(pattern, data, E_MATCH);
1966 }
1967
1968 int ast_extension_close(const char *pattern, const char *data, int needmore)
1969 {
1970         if (needmore != E_MATCHMORE && needmore != E_CANMATCH)
1971                 ast_log(LOG_WARNING, "invalid argument %d\n", needmore);
1972         return extension_match_core(pattern, data, needmore);
1973 }
1974
1975 struct fake_context /* this struct is purely for matching in the hashtab */
1976 {
1977         ast_rwlock_t lock;                      
1978         struct ast_exten *root;         
1979         struct ast_hashtab *root_table;            
1980         struct match_char *pattern_tree;       
1981         struct ast_context *next;       
1982         struct ast_include *includes;           
1983         struct ast_ignorepat *ignorepats;       
1984         const char *registrar;
1985         int refcount;
1986         AST_LIST_HEAD_NOLOCK(, ast_sw) alts;    
1987         ast_mutex_t macrolock;          
1988         char name[256];         
1989 };
1990
1991 struct ast_context *ast_context_find(const char *name)
1992 {
1993         struct ast_context *tmp = NULL;
1994         struct fake_context item;
1995         strncpy(item.name,name,256);
1996         ast_rdlock_contexts();
1997         if( contexts_table ) {
1998                 tmp = ast_hashtab_lookup(contexts_table,&item);
1999         } else {
2000                 while ( (tmp = ast_walk_contexts(tmp)) ) {
2001                         if (!name || !strcasecmp(name, tmp->name))
2002                                 break;
2003                 }
2004         }
2005         ast_unlock_contexts();
2006         return tmp;
2007 }
2008
2009 #define STATUS_NO_CONTEXT       1
2010 #define STATUS_NO_EXTENSION     2
2011 #define STATUS_NO_PRIORITY      3
2012 #define STATUS_NO_LABEL         4
2013 #define STATUS_SUCCESS          5
2014
2015 static int matchcid(const char *cidpattern, const char *callerid)
2016 {
2017         /* If the Caller*ID pattern is empty, then we're matching NO Caller*ID, so
2018            failing to get a number should count as a match, otherwise not */
2019
2020         if (ast_strlen_zero(callerid))
2021                 return ast_strlen_zero(cidpattern) ? 1 : 0;
2022
2023         return ast_extension_match(cidpattern, callerid);
2024 }
2025
2026 struct ast_exten *pbx_find_extension(struct ast_channel *chan,
2027         struct ast_context *bypass, struct pbx_find_info *q,
2028         const char *context, const char *exten, int priority,
2029         const char *label, const char *callerid, enum ext_match_t action)
2030 {
2031         int x, res;
2032         struct ast_context *tmp = NULL;
2033         struct ast_exten *e = NULL, *eroot = NULL;
2034         struct ast_include *i = NULL;
2035         struct ast_sw *sw = NULL;
2036         struct ast_exten pattern = {NULL, };
2037         struct scoreboard score = {0, };
2038         struct ast_str *tmpdata = NULL;
2039
2040         pattern.label = label;
2041         pattern.priority = priority;
2042 #ifdef NEED_DEBUG_HERE
2043         ast_log(LOG_NOTICE,"Looking for cont/ext/prio/label/action = %s/%s/%d/%s/%d\n", context, exten, priority, label, (int)action);
2044 #endif
2045
2046         if (ast_strlen_zero(exten))
2047                 return NULL;
2048
2049         /* Initialize status if appropriate */
2050         if (q->stacklen == 0) {
2051                 q->status = STATUS_NO_CONTEXT;
2052                 q->swo = NULL;
2053                 q->data = NULL;
2054                 q->foundcontext = NULL;
2055         } else if (q->stacklen >= AST_PBX_MAX_STACK) {
2056                 ast_log(LOG_WARNING, "Maximum PBX stack exceeded\n");
2057                 return NULL;
2058         }
2059
2060         /* Check first to see if we've already been checked */
2061         for (x = 0; x < q->stacklen; x++) {
2062                 if (!strcasecmp(q->incstack[x], context))
2063                         return NULL;
2064         }
2065
2066         if (bypass)     /* bypass means we only look there */
2067                 tmp = bypass;
2068         else {  /* look in contexts */
2069                 struct fake_context item;
2070                 strncpy(item.name,context,256);
2071                 tmp = ast_hashtab_lookup(contexts_table,&item);
2072 #ifdef NOTNOW
2073                 tmp = NULL;
2074                 while ((tmp = ast_walk_contexts(tmp)) ) {
2075                         if (!strcmp(tmp->name, context))
2076                                 break;
2077                 }
2078 #endif
2079                 if (!tmp)
2080                         return NULL;
2081                 
2082         }
2083
2084         if (q->status < STATUS_NO_EXTENSION)
2085                 q->status = STATUS_NO_EXTENSION;
2086         
2087         /* Do a search for matching extension */
2088
2089         eroot = NULL;
2090         score.total_specificity = 0;
2091         score.exten = 0;
2092         score.total_length = 0;
2093         if (!tmp->pattern_tree && tmp->root_table)
2094         {
2095                 create_match_char_tree(tmp);
2096 #ifdef NEED_DEBUG
2097                 ast_log(LOG_DEBUG,"Tree Created in context %s:\n", context);
2098                 log_match_char_tree(tmp->pattern_tree," ");
2099 #endif
2100         }
2101 #ifdef NEED_DEBUG
2102         ast_log(LOG_NOTICE,"The Trie we are searching in:\n");
2103         log_match_char_tree(tmp->pattern_tree, "::  ");
2104 #endif
2105
2106         do {
2107                 if (!ast_strlen_zero(overrideswitch)) {
2108                         char *osw = ast_strdupa(overrideswitch), *name;
2109                         struct ast_switch *asw;
2110                         ast_switch_f *aswf = NULL;
2111                         char *datap;
2112                         int eval = 0;
2113
2114                         name = strsep(&osw, "/");
2115                         asw = pbx_findswitch(name);
2116
2117                         if (!asw) {
2118                                 ast_log(LOG_WARNING, "No such switch '%s'\n", name);
2119                                 break;
2120                         }
2121
2122                         if (osw && strchr(osw, '$')) {
2123                                 eval = 1;
2124                         }
2125
2126                         if (eval && !(tmpdata = ast_str_thread_get(&switch_data, 512))) {
2127                                 ast_log(LOG_WARNING, "Can't evaluate overrideswitch?!");
2128                                 break;
2129                         } else if (eval) {
2130                                 /* Substitute variables now */
2131                                 pbx_substitute_variables_helper(chan, osw, tmpdata->str, tmpdata->len);
2132                                 datap = tmpdata->str;
2133                         } else {
2134                                 datap = osw;
2135                         }
2136
2137                         /* equivalent of extension_match_core() at the switch level */
2138                         if (action == E_CANMATCH)
2139                                 aswf = asw->canmatch;
2140                         else if (action == E_MATCHMORE)
2141                                 aswf = asw->matchmore;
2142                         else /* action == E_MATCH */
2143                                 aswf = asw->exists;
2144                         if (!aswf) {
2145                                 res = 0;
2146                         } else {
2147                                 if (chan) {
2148                                         ast_autoservice_start(chan);
2149                                 }
2150                                 res = aswf(chan, context, exten, priority, callerid, datap);
2151                                 if (chan) {
2152                                         ast_autoservice_stop(chan);
2153                                 }
2154                         }
2155                         if (res) {      /* Got a match */
2156                                 q->swo = asw;
2157                                 q->data = datap;
2158                                 q->foundcontext = context;
2159                                 /* XXX keep status = STATUS_NO_CONTEXT ? */
2160                                 return NULL;
2161                         }
2162                 }
2163         } while (0);
2164
2165         if (extenpatternmatchnew) {
2166                 new_find_extension(exten, &score, tmp->pattern_tree, 0, 0, callerid, label, action);
2167                 eroot = score.exten;
2168                 
2169                 if (score.last_char == '!' && action == E_MATCHMORE) {
2170                         /* We match an extension ending in '!'.
2171                          * The decision in this case is final and is NULL (no match).
2172                          */
2173 #ifdef NEED_DEBUG_HERE
2174                         ast_log(LOG_NOTICE,"Returning MATCHMORE NULL with exclamation point.\n");
2175 #endif
2176                         return NULL;
2177                 }
2178                 
2179                 if (!eroot && (action == E_CANMATCH || action == E_MATCHMORE) && score.canmatch_exten) {
2180                         q->status = STATUS_SUCCESS;
2181 #ifdef NEED_DEBUG_HERE
2182                         ast_log(LOG_NOTICE,"Returning CANMATCH exten %s\n", score.canmatch_exten->exten);
2183 #endif
2184                         return score.canmatch_exten;
2185                 }
2186                 
2187                 if ((action == E_MATCHMORE || action == E_CANMATCH)  && eroot) {
2188                         if (score.node) {
2189                                 struct ast_exten *z = trie_find_next_match(score.node);
2190                                 if (z) {
2191 #ifdef NEED_DEBUG_HERE
2192                                         ast_log(LOG_NOTICE,"Returning CANMATCH/MATCHMORE next_match exten %s\n", z->exten);
2193 #endif
2194                                 } else {
2195                                         if (score.canmatch_exten) {
2196 #ifdef NEED_DEBUG_HERE
2197                                                 ast_log(LOG_NOTICE,"Returning CANMATCH/MATCHMORE canmatchmatch exten %s(%p)\n", score.canmatch_exten->exten, score.canmatch_exten);
2198 #endif
2199                                                 return score.canmatch_exten;
2200                                         } else {
2201 #ifdef NEED_DEBUG_HERE
2202                                                 ast_log(LOG_NOTICE,"Returning CANMATCH/MATCHMORE next_match exten NULL\n");
2203 #endif
2204                                         }
2205                                 }
2206                                 return z;
2207                         }
2208 #ifdef NEED_DEBUG_HERE
2209                         ast_log(LOG_NOTICE,"Returning CANMATCH/MATCHMORE NULL (no next_match)\n");
2210 #endif
2211                         return NULL;  /* according to the code, complete matches are null matches in MATCHMORE mode */
2212                 }
2213                 
2214                 if (eroot) {
2215                         /* found entry, now look for the right priority */
2216                         if (q->status < STATUS_NO_PRIORITY)
2217                                 q->status = STATUS_NO_PRIORITY;
2218                         e = NULL;
2219                         if (action == E_FINDLABEL && label ) {
2220                                 if (q->status < STATUS_NO_LABEL)
2221                                         q->status = STATUS_NO_LABEL;
2222                                 e = ast_hashtab_lookup(eroot->peer_label_table, &pattern);
2223                         } else {
2224                                 e = ast_hashtab_lookup(eroot->peer_table, &pattern);
2225                         }
2226                         if (e) {        /* found a valid match */
2227                                 q->status = STATUS_SUCCESS;
2228                                 q->foundcontext = context;
2229 #ifdef NEED_DEBUG_HERE
2230                                 ast_log(LOG_NOTICE,"Returning complete match of exten %s\n", e->exten);
2231 #endif
2232                                 return e;
2233                         }
2234                 }
2235         } else {   /* the old/current default exten pattern match algorithm */
2236                 
2237                 /* scan the list trying to match extension and CID */
2238                 eroot = NULL;
2239                 while ( (eroot = ast_walk_context_extensions(tmp, eroot)) ) {
2240                         int match = extension_match_core(eroot->exten, exten, action);
2241                         /* 0 on fail, 1 on match, 2 on earlymatch */
2242                         
2243                         if (!match || (eroot->matchcid && !matchcid(eroot->cidmatch, callerid)))
2244                                 continue;       /* keep trying */
2245                         if (match == 2 && action == E_MATCHMORE) {
2246                                 /* We match an extension ending in '!'.
2247                                  * The decision in this case is final and is NULL (no match).
2248                                  */
2249                                 return NULL;
2250                         }
2251                         /* found entry, now look for the right priority */
2252                         if (q->status < STATUS_NO_PRIORITY)
2253                                 q->status = STATUS_NO_PRIORITY;
2254                         e = NULL;
2255                         if (action == E_FINDLABEL && label ) {
2256                                 if (q->status < STATUS_NO_LABEL)
2257                                         q->status = STATUS_NO_LABEL;
2258                                 e = ast_hashtab_lookup(eroot->peer_label_table, &pattern);
2259                         } else {
2260                                 e = ast_hashtab_lookup(eroot->peer_table, &pattern);
2261                         }
2262 #ifdef NOTNOW
2263                         while ( (e = ast_walk_extension_priorities(eroot, e)) ) {
2264                                 /* Match label or priority */
2265                                 if (action == E_FINDLABEL) {
2266                                         if (q->status < STATUS_NO_LABEL)
2267                                                 q->status = STATUS_NO_LABEL;
2268                                         if (label && e->label && !strcmp(label, e->label))
2269                                                 break;  /* found it */
2270                                 } else if (e->priority == priority) {
2271                                         break;  /* found it */
2272                                 } /* else keep searching */
2273                         }
2274 #endif
2275                         if (e) {        /* found a valid match */
2276                                 q->status = STATUS_SUCCESS;
2277                                 q->foundcontext = context;
2278                                 return e;
2279                         }
2280                 }
2281         }
2282         
2283         
2284         /* Check alternative switches */
2285         AST_LIST_TRAVERSE(&tmp->alts, sw, list) {
2286                 struct ast_switch *asw = pbx_findswitch(sw->name);
2287                 ast_switch_f *aswf = NULL;
2288                 char *datap;
2289
2290                 if (!asw) {
2291                         ast_log(LOG_WARNING, "No such switch '%s'\n", sw->name);
2292                         continue;
2293                 }
2294                 /* Substitute variables now */
2295                 
2296                 if (sw->eval) {
2297                         if (!(tmpdata = ast_str_thread_get(&switch_data, 512))) {
2298                                 ast_log(LOG_WARNING, "Can't evaluate switch?!");
2299                                 continue;
2300                         }
2301                         pbx_substitute_variables_helper(chan, sw->data, tmpdata->str, tmpdata->len);
2302                 }
2303
2304                 /* equivalent of extension_match_core() at the switch level */
2305                 if (action == E_CANMATCH)
2306                         aswf = asw->canmatch;
2307                 else if (action == E_MATCHMORE)
2308                         aswf = asw->matchmore;
2309                 else /* action == E_MATCH */
2310                         aswf = asw->exists;
2311                 datap = sw->eval ? tmpdata->str : sw->data;
2312                 if (!aswf)
2313                         res = 0;
2314                 else {
2315                         if (chan)
2316                                 ast_autoservice_start(chan);
2317                         res = aswf(chan, context, exten, priority, callerid, datap);
2318                         if (chan)
2319                                 ast_autoservice_stop(chan);
2320                 }
2321                 if (res) {      /* Got a match */
2322                         q->swo = asw;
2323                         q->data = datap;
2324                         q->foundcontext = context;
2325                         /* XXX keep status = STATUS_NO_CONTEXT ? */
2326                         return NULL;
2327                 }
2328         }
2329         q->incstack[q->stacklen++] = tmp->name; /* Setup the stack */
2330         /* Now try any includes we have in this context */
2331         for (i = tmp->includes; i; i = i->next) {
2332                 if (include_valid(i)) {
2333                         if ((e = pbx_find_extension(chan, bypass, q, i->rname, exten, priority, label, callerid, action))) {
2334 #ifdef NEED_DEBUG_HERE
2335                                 ast_log(LOG_NOTICE,"Returning recursive match of %s\n", e->exten);
2336 #endif
2337                                 return e;
2338                         }
2339                         if (q->swo)
2340                                 return NULL;
2341                 }
2342         }
2343         return NULL;
2344 }
2345
2346 /*! 
2347  * \brief extract offset:length from variable name.
2348  * \return 1 if there is a offset:length part, which is
2349  * trimmed off (values go into variables)
2350  */
2351 static int parse_variable_name(char *var, int *offset, int *length, int *isfunc)
2352 {
2353         int parens = 0;
2354
2355         *offset = 0;
2356         *length = INT_MAX;
2357         *isfunc = 0;
2358         for (; *var; var++) {
2359                 if (*var == '(') {
2360                         (*isfunc)++;
2361                         parens++;
2362                 } else if (*var == ')') {
2363                         parens--;
2364                 } else if (*var == ':' && parens == 0) {
2365                         *var++ = '\0';
2366                         sscanf(var, "%d:%d", offset, length);
2367                         return 1; /* offset:length valid */
2368                 }
2369         }
2370         return 0;
2371 }
2372
2373 /*! 
2374  *\brief takes a substring. It is ok to call with value == workspace.
2375  * \param value
2376  * \param offset < 0 means start from the end of the string and set the beginning
2377  *   to be that many characters back.
2378  * \param length is the length of the substring, a value less than 0 means to leave
2379  * that many off the end.
2380  * \param workspace
2381  * \param workspace_len
2382  * Always return a copy in workspace.
2383  */
2384 static char *substring(const char *value, int offset, int length, char *workspace, size_t workspace_len)
2385 {
2386         char *ret = workspace;
2387         int lr; /* length of the input string after the copy */
2388
2389         ast_copy_string(workspace, value, workspace_len); /* always make a copy */
2390
2391         lr = strlen(ret); /* compute length after copy, so we never go out of the workspace */
2392
2393         /* Quick check if no need to do anything */
2394         if (offset == 0 && length >= lr)        /* take the whole string */
2395                 return ret;
2396
2397         if (offset < 0) {       /* translate negative offset into positive ones */
2398                 offset = lr + offset;
2399                 if (offset < 0) /* If the negative offset was greater than the length of the string, just start at the beginning */
2400                         offset = 0;
2401         }
2402
2403         /* too large offset result in empty string so we know what to return */
2404         if (offset >= lr)
2405                 return ret + lr;        /* the final '\0' */
2406
2407         ret += offset;          /* move to the start position */
2408         if (length >= 0 && length < lr - offset)        /* truncate if necessary */
2409                 ret[length] = '\0';
2410         else if (length < 0) {
2411                 if (lr > offset - length) /* After we remove from the front and from the rear, is there anything left? */
2412                         ret[lr + length - offset] = '\0';
2413                 else
2414                         ret[0] = '\0';
2415         }
2416
2417         return ret;
2418 }
2419
2420 /*! \brief  Support for Asterisk built-in variables in the dialplan
2421
2422 \note   See also
2423         - \ref AstVar   Channel variables
2424         - \ref AstCauses The HANGUPCAUSE variable
2425  */
2426 void pbx_retrieve_variable(struct ast_channel *c, const char *var, char **ret, char *workspace, int workspacelen, struct varshead *headp)
2427 {
2428         const char not_found = '\0';
2429         char *tmpvar;
2430         const char *s;  /* the result */
2431         int offset, length;
2432         int i, need_substring;
2433         struct varshead *places[2] = { headp, &globals };       /* list of places where we may look */
2434
2435         if (c) {
2436                 ast_channel_lock(c);
2437                 places[0] = &c->varshead;
2438         }
2439         /*
2440          * Make a copy of var because parse_variable_name() modifies the string.
2441          * Then if called directly, we might need to run substring() on the result;
2442          * remember this for later in 'need_substring', 'offset' and 'length'
2443          */
2444         tmpvar = ast_strdupa(var);      /* parse_variable_name modifies the string */
2445         need_substring = parse_variable_name(tmpvar, &offset, &length, &i /* ignored */);
2446
2447         /*
2448          * Look first into predefined variables, then into variable lists.
2449          * Variable 's' points to the result, according to the following rules:
2450          * s == &not_found (set at the beginning) means that we did not find a
2451          *      matching variable and need to look into more places.
2452          * If s != &not_found, s is a valid result string as follows:
2453          * s = NULL if the variable does not have a value;
2454          *      you typically do this when looking for an unset predefined variable.
2455          * s = workspace if the result has been assembled there;
2456          *      typically done when the result is built e.g. with an snprintf(),
2457          *      so we don't need to do an additional copy.
2458          * s != workspace in case we have a string, that needs to be copied
2459          *      (the ast_copy_string is done once for all at the end).
2460          *      Typically done when the result is already available in some string.
2461          */
2462         s = &not_found; /* default value */
2463         if (c) {        /* This group requires a valid channel */
2464                 /* Names with common parts are looked up a piece at a time using strncmp. */
2465                 if (!strncmp(var, "CALL", 4)) {
2466                         if (!strncmp(var + 4, "ING", 3)) {
2467                                 if (!strcmp(var + 7, "PRES")) {                 /* CALLINGPRES */
2468                                         snprintf(workspace, workspacelen, "%d", c->cid.cid_pres);
2469                                         s = workspace;
2470                                 } else if (!strcmp(var + 7, "ANI2")) {          /* CALLINGANI2 */
2471                                         snprintf(workspace, workspacelen, "%d", c->cid.cid_ani2);
2472                                         s = workspace;
2473                                 } else if (!strcmp(var + 7, "TON")) {           /* CALLINGTON */
2474                                         snprintf(workspace, workspacelen, "%d", c->cid.cid_ton);
2475                                         s = workspace;
2476                                 } else if (!strcmp(var + 7, "TNS")) {           /* CALLINGTNS */
2477                                         snprintf(workspace, workspacelen, "%d", c->cid.cid_tns);
2478                                         s = workspace;
2479                                 }
2480                         }
2481                 } else if (!strcmp(var, "HINT")) {
2482                         s = ast_get_hint(workspace, workspacelen, NULL, 0, c, c->context, c->exten) ? workspace : NULL;
2483                 } else if (!strcmp(var, "HINTNAME")) {
2484                         s = ast_get_hint(NULL, 0, workspace, workspacelen, c, c->context, c->exten) ? workspace : NULL;
2485                 } else if (!strcmp(var, "EXTEN")) {
2486                         s = c->exten;
2487                 } else if (!strcmp(var, "CONTEXT")) {
2488                         s = c->context;
2489                 } else if (!strcmp(var, "PRIORITY")) {
2490                         snprintf(workspace, workspacelen, "%d", c->priority);
2491                         s = workspace;
2492                 } else if (!strcmp(var, "CHANNEL")) {
2493                         s = c->name;
2494                 } else if (!strcmp(var, "UNIQUEID")) {
2495                         s = c->uniqueid;
2496                 } else if (!strcmp(var, "HANGUPCAUSE")) {
2497                         snprintf(workspace, workspacelen, "%d", c->hangupcause);
2498                         s = workspace;
2499                 }
2500         }
2501         if (s == &not_found) { /* look for more */
2502                 if (!strcmp(var, "EPOCH")) {
2503                         snprintf(workspace, workspacelen, "%u",(int)time(NULL));
2504                         s = workspace;
2505                 } else if (!strcmp(var, "SYSTEMNAME")) {
2506                         s = ast_config_AST_SYSTEM_NAME;
2507                 } else if (!strcmp(var, "ENTITYID")) {
2508                         ast_eid_to_str(workspace, workspacelen, &g_eid);
2509                         s = workspace;
2510                 }
2511         }
2512         /* if not found, look into chanvars or global vars */
2513         for (i = 0; s == &not_found && i < ARRAY_LEN(places); i++) {
2514                 struct ast_var_t *variables;
2515                 if (!places[i])
2516                         continue;
2517                 if (places[i] == &globals)
2518                         ast_rwlock_rdlock(&globalslock);
2519                 AST_LIST_TRAVERSE(places[i], variables, entries) {
2520                         if (!strcasecmp(ast_var_name(variables), var)) {
2521                                 s = ast_var_value(variables);
2522                                 break;
2523                         }
2524                 }
2525                 if (places[i] == &globals)
2526                         ast_rwlock_unlock(&globalslock);
2527         }
2528         if (s == &not_found || s == NULL)
2529                 *ret = NULL;
2530         else {
2531                 if (s != workspace)
2532                         ast_copy_string(workspace, s, workspacelen);
2533                 *ret = workspace;
2534                 if (need_substring)
2535                         *ret = substring(*ret, offset, length, workspace, workspacelen);
2536         }
2537
2538         if (c)
2539                 ast_channel_unlock(c);
2540 }
2541
2542 static void exception_store_free(void *data)
2543 {
2544         struct pbx_exception *exception = data;
2545         ast_string_field_free_memory(exception);
2546         ast_free(exception);
2547 }
2548
2549 static struct ast_datastore_info exception_store_info = {
2550         .type = "EXCEPTION",
2551         .destroy = exception_store_free,
2552 };
2553
2554 int pbx_builtin_raise_exception(struct ast_channel *chan, void *vreason)
2555 {
2556         const char *reason = vreason;
2557         struct ast_datastore *ds = ast_channel_datastore_find(chan, &exception_store_info, NULL);
2558         struct pbx_exception *exception = NULL;
2559
2560         if (!ds) {
2561                 ds = ast_datastore_alloc(&exception_store_info, NULL);
2562                 if (!ds)
2563                         return -1;
2564                 exception = ast_calloc(1, sizeof(struct pbx_exception));
2565                 if (!exception) {
2566                         ast_datastore_free(ds);
2567                         return -1;
2568                 }
2569                 if (ast_string_field_init(exception, 128)) {
2570                         ast_free(exception);
2571                         ast_datastore_free(ds);
2572                         return -1;
2573                 }
2574                 ds->data = exception;
2575                 ast_channel_datastore_add(chan, ds);
2576         } else
2577                 exception = ds->data;
2578
2579         ast_string_field_set(exception, reason, reason);
2580         ast_string_field_set(exception, context, chan->context);
2581         ast_string_field_set(exception, exten, chan->exten);
2582         exception->priority = chan->priority;
2583         set_ext_pri(chan, "e", 0);
2584         return 0;
2585 }
2586
2587 static int acf_exception_read(struct ast_channel *chan, const char *name, char *data, char *buf, size_t buflen)
2588 {
2589         struct ast_datastore *ds = ast_channel_datastore_find(chan, &exception_store_info, NULL);
2590         struct pbx_exception *exception = NULL;
2591         if (!ds || !ds->data)
2592                 return -1;
2593         exception = ds->data;
2594         if (!strcasecmp(data, "REASON"))
2595                 ast_copy_string(buf, exception->reason, buflen);
2596         else if (!strcasecmp(data, "CONTEXT"))
2597                 ast_copy_string(buf, exception->context, buflen);
2598         else if (!strncasecmp(data, "EXTEN", 5))
2599                 ast_copy_string(buf, exception->exten, buflen);
2600         else if (!strcasecmp(data, "PRIORITY"))
2601                 snprintf(buf, buflen, "%d", exception->priority);
2602         else
2603                 return -1;
2604         return 0;
2605 }
2606
2607 static struct ast_custom_function exception_function = {
2608         .name = "EXCEPTION",
2609         .synopsis = "Retrieve the details of the current dialplan exception",
2610         .desc =
2611 "The following fields are available for retrieval:\n"
2612 "  reason    INVALID, ERROR, RESPONSETIMEOUT, ABSOLUTETIMEOUT, or custom\n"
2613 "               value set by the RaiseException() application\n"
2614 "  context   The context executing when the exception occurred\n"
2615 "  exten     The extension executing when the exception occurred\n"
2616 "  priority  The numeric priority executing when the exception occurred\n",
2617         .syntax = "EXCEPTION(<field>)",
2618         .read = acf_exception_read,
2619 };
2620
2621 static char *handle_show_functions(struct ast_cli_entry *e, int cmd, struct ast_cli_args *a)
2622 {
2623         struct ast_custom_function *acf;
2624         int count_acf = 0;
2625         int like = 0;
2626
2627         switch (cmd) {
2628         case CLI_INIT:
2629                 e->command = "core show functions [like]";
2630                 e->usage = 
2631                         "Usage: core show functions [like <text>]\n"
2632                         "       List builtin functions, optionally only those matching a given string\n";
2633                 return NULL;
2634         case CLI_GENERATE:
2635                 return NULL;
2636         }
2637
2638         if (a->argc == 5 && (!strcmp(a->argv[3], "like")) ) {
2639                 like = 1;
2640         } else if (a->argc != 3) {
2641                 return CLI_SHOWUSAGE;
2642         }
2643
2644         ast_cli(a->fd, "%s Custom Functions:\n--------------------------------------------------------------------------------\n", like ? "Matching" : "Installed");
2645
2646         AST_RWLIST_RDLOCK(&acf_root);
2647         AST_RWLIST_TRAVERSE(&acf_root, acf, acflist) {
2648                 if (!like || strstr(acf->name, a->argv[4])) {
2649                         count_acf++;
2650                         ast_cli(a->fd, "%-20.20s  %-35.35s  %s\n", acf->name, acf->syntax, acf->synopsis);
2651                 }
2652         }
2653         AST_RWLIST_UNLOCK(&acf_root);
2654
2655         ast_cli(a->fd, "%d %scustom functions installed.\n", count_acf, like ? "matching " : "");
2656
2657         return CLI_SUCCESS;
2658 }
2659
2660 static char *handle_show_function(struct ast_cli_entry *e, int cmd, struct ast_cli_args *a)
2661 {
2662         struct ast_custom_function *acf;
2663         /* Maximum number of characters added by terminal coloring is 22 */
2664         char infotitle[64 + AST_MAX_APP + 22], syntitle[40], destitle[40];
2665         char info[64 + AST_MAX_APP], *synopsis = NULL, *description = NULL;
2666         char stxtitle[40], *syntax = NULL;
2667         int synopsis_size, description_size, syntax_size;
2668         char *ret = NULL;
2669         int which = 0;
2670         int wordlen;
2671
2672         switch (cmd) {
2673         case CLI_INIT:
2674                 e->command = "core show function";
2675                 e->usage = 
2676                         "Usage: core show function <function>\n"
2677                         "       Describe a particular dialplan function.\n";
2678                 return NULL;
2679         case CLI_GENERATE:      
2680                 wordlen = strlen(a->word);
2681                 /* case-insensitive for convenience in this 'complete' function */
2682                 AST_RWLIST_RDLOCK(&acf_root);
2683                 AST_RWLIST_TRAVERSE(&acf_root, acf, acflist) {
2684                         if (!strncasecmp(a->word, acf->name, wordlen) && ++which > a->n) {
2685                                 ret = ast_strdup(acf->name);
2686                                 break;
2687                         }
2688                 }
2689                 AST_RWLIST_UNLOCK(&acf_root);
2690
2691                 return ret;
2692         }
2693
2694         if (a->argc < 4)
2695                 return CLI_SHOWUSAGE;
2696
2697         if (!(acf = ast_custom_function_find(a->argv[3]))) {
2698                 ast_cli(a->fd, "No function by that name registered.\n");
2699                 return CLI_FAILURE;
2700
2701         }
2702
2703         if (acf->synopsis)
2704                 synopsis_size = strlen(acf->synopsis) + 23;
2705         else
2706                 synopsis_size = strlen("Not available") + 23;
2707         synopsis = alloca(synopsis_size);
2708
2709         if (acf->desc)
2710                 description_size = strlen(acf->desc) + 23;
2711         else
2712                 description_size = strlen("Not available") + 23;
2713         description = alloca(description_size);
2714
2715         if (acf->syntax)
2716                 syntax_size = strlen(acf->syntax) + 23;
2717         else
2718                 syntax_size = strlen("Not available") + 23;
2719         syntax = alloca(syntax_size);
2720
2721         snprintf(info, 64 + AST_MAX_APP, "\n  -= Info about function '%s' =- \n\n", acf->name);
2722         term_color(infotitle, info, COLOR_MAGENTA, 0, 64 + AST_MAX_APP + 22);
2723         term_color(stxtitle, "[Syntax]\n", COLOR_MAGENTA, 0, 40);
2724         term_color(syntitle, "[Synopsis]\n", COLOR_MAGENTA, 0, 40);
2725         term_color(destitle, "[Description]\n", COLOR_MAGENTA, 0, 40);
2726         term_color(syntax,
2727                    acf->syntax ? acf->syntax : "Not available",
2728                    COLOR_CYAN, 0, syntax_size);
2729         term_color(synopsis,
2730                    acf->synopsis ? acf->synopsis : "Not available",
2731                    COLOR_CYAN, 0, synopsis_size);
2732         term_color(description,
2733                    acf->desc ? acf->desc : "Not available",
2734                    COLOR_CYAN, 0, description_size);
2735
2736         ast_cli(a->fd,"%s%s%s\n\n%s%s\n\n%s%s\n", infotitle, stxtitle, syntax, syntitle, synopsis, destitle, description);
2737
2738         return CLI_SUCCESS;
2739 }
2740
2741 struct ast_custom_function *ast_custom_function_find(const char *name)
2742 {
2743         struct ast_custom_function *acf = NULL;
2744
2745         AST_RWLIST_RDLOCK(&acf_root);
2746         AST_RWLIST_TRAVERSE(&acf_root, acf, acflist) {
2747                 if (!strcmp(name, acf->name))
2748                         break;
2749         }
2750         AST_RWLIST_UNLOCK(&acf_root);
2751
2752         return acf;
2753 }
2754
2755 int ast_custom_function_unregister(struct ast_custom_function *acf)
2756 {
2757         struct ast_custom_function *cur;
2758
2759         if (!acf)
2760                 return -1;
2761
2762         AST_RWLIST_WRLOCK(&acf_root);
2763         if ((cur = AST_RWLIST_REMOVE(&acf_root, acf, acflist)))
2764                 ast_verb(2, "Unregistered custom function %s\n", cur->name);
2765         AST_RWLIST_UNLOCK(&acf_root);
2766
2767         return cur ? 0 : -1;
2768 }
2769
2770 int __ast_custom_function_register(struct ast_custom_function *acf, struct ast_module *mod)
2771 {
2772         struct ast_custom_function *cur;
2773         char tmps[80];
2774
2775         if (!acf)
2776                 return -1;
2777
2778         acf->mod = mod;
2779
2780         AST_RWLIST_WRLOCK(&acf_root);
2781
2782         AST_RWLIST_TRAVERSE(&acf_root, cur, acflist) {
2783                 if (!strcmp(acf->name, cur->name)) {
2784                         ast_log(LOG_ERROR, "Function %s already registered.\n", acf->name);
2785                         AST_RWLIST_UNLOCK(&acf_root);
2786                         return -1;
2787                 }
2788         }
2789
2790         /* Store in alphabetical order */
2791         AST_RWLIST_TRAVERSE_SAFE_BEGIN(&acf_root, cur, acflist) {
2792                 if (strcasecmp(acf->name, cur->name) < 0) {
2793                         AST_RWLIST_INSERT_BEFORE_CURRENT(acf, acflist);
2794                         break;
2795                 }
2796         }
2797         AST_RWLIST_TRAVERSE_SAFE_END;
2798         if (!cur)
2799                 AST_RWLIST_INSERT_TAIL(&acf_root, acf, acflist);
2800
2801         AST_RWLIST_UNLOCK(&acf_root);
2802
2803         ast_verb(2, "Registered custom function '%s'\n", term_color(tmps, acf->name, COLOR_BRCYAN, 0, sizeof(tmps)));
2804
2805         return 0;
2806 }
2807
2808 /*! \brief return a pointer to the arguments of the function,
2809  * and terminates the function name with '\\0'
2810  */
2811 static char *func_args(char *function)
2812 {
2813         char *args = strchr(function, '(');
2814
2815         if (!args)
2816                 ast_log(LOG_WARNING, "Function doesn't contain parentheses.  Assuming null argument.\n");
2817         else {
2818                 char *p;
2819                 *args++ = '\0';
2820                 if ((p = strrchr(args, ')')) )
2821                         *p = '\0';
2822                 else
2823                         ast_log(LOG_WARNING, "Can't find trailing parenthesis?\n");
2824         }
2825         return args;
2826 }
2827
2828 int ast_func_read(struct ast_channel *chan, const char *function, char *workspace, size_t len)
2829 {
2830         char *copy = ast_strdupa(function);
2831         char *args = func_args(copy);
2832         struct ast_custom_function *acfptr = ast_custom_function_find(copy);
2833
2834         if (acfptr == NULL)
2835                 ast_log(LOG_ERROR, "Function %s not registered\n", copy);
2836         else if (!acfptr->read)
2837                 ast_log(LOG_ERROR, "Function %s cannot be read\n", copy);
2838         else {
2839                 int res;
2840                 struct ast_module_user *u = NULL;
2841                 if (acfptr->mod)
2842                         u = __ast_module_user_add(acfptr->mod, chan);
2843                 res = acfptr->read(chan, copy, args, workspace, len);
2844                 if (acfptr->mod && u)
2845                         __ast_module_user_remove(acfptr->mod, u);
2846                 return res;
2847         }
2848         return -1;
2849 }
2850
2851 int ast_func_write(struct ast_channel *chan, const char *function, const char *value)
2852 {
2853         char *copy = ast_strdupa(function);
2854         char *args = func_args(copy);
2855         struct ast_custom_function *acfptr = ast_custom_function_find(copy);
2856
2857         if (acfptr == NULL)
2858                 ast_log(LOG_ERROR, "Function %s not registered\n", copy);
2859         else if (!acfptr->write)
2860                 ast_log(LOG_ERROR, "Function %s cannot be written to\n", copy);
2861         else {
2862                 int res;
2863                 struct ast_module_user *u = NULL;
2864                 if (acfptr->mod)
2865                         u = __ast_module_user_add(acfptr->mod, chan);
2866                 res = acfptr->write(chan, copy, args, value);
2867                 if (acfptr->mod && u)
2868                         __ast_module_user_remove(acfptr->mod, u);
2869                 return res;
2870         }
2871
2872         return -1;
2873 }
2874
2875 static void pbx_substitute_variables_helper_full(struct ast_channel *c, struct varshead *headp, const char *cp1, char *cp2, int count)
2876 {
2877         /* Substitutes variables into cp2, based on string cp1, cp2 NO LONGER NEEDS TO BE ZEROED OUT!!!!  */
2878         char *cp4;
2879         const char *tmp, *whereweare;
2880         int length, offset, offset2, isfunction;
2881         char *workspace = NULL;
2882         char *ltmp = NULL, *var = NULL;
2883         char *nextvar, *nextexp, *nextthing;
2884         char *vars, *vare;
2885         int pos, brackets, needsub, len;
2886         
2887         *cp2 = 0; /* just in case nothing ends up there */
2888         whereweare=tmp=cp1;
2889         while (!ast_strlen_zero(whereweare) && count) {
2890                 /* Assume we're copying the whole remaining string */
2891                 pos = strlen(whereweare);
2892                 nextvar = NULL;
2893                 nextexp = NULL;
2894                 nextthing = strchr(whereweare, '$');
2895                 if (nextthing) {
2896                         switch (nextthing[1]) {
2897                         case '{':
2898                                 nextvar = nextthing;
2899                                 pos = nextvar - whereweare;
2900                                 break;
2901                         case '[':
2902                                 nextexp = nextthing;
2903                                 pos = nextexp - whereweare;
2904                                 break;
2905                         default:
2906                                 pos = 1;
2907                         }
2908                 }
2909
2910                 if (pos) {
2911                         /* Can't copy more than 'count' bytes */
2912                         if (pos > count)
2913                                 pos = count;
2914
2915                         /* Copy that many bytes */
2916                         memcpy(cp2, whereweare, pos);
2917
2918                         count -= pos;
2919                         cp2 += pos;
2920                         whereweare += pos;
2921                         *cp2 = 0;
2922                 }
2923
2924                 if (nextvar) {
2925                         /* We have a variable.  Find the start and end, and determine
2926                            if we are going to have to recursively call ourselves on the
2927                            contents */
2928                         vars = vare = nextvar + 2;
2929                         brackets = 1;
2930                         needsub = 0;
2931
2932                         /* Find the end of it */
2933                         while (brackets && *vare) {
2934                                 if ((vare[0] == '$') && (vare[1] == '{')) {
2935                                         needsub++;
2936                                 } else if (vare[0] == '{') {
2937                                         brackets++;
2938                                 } else if (vare[0] == '}') {
2939                                         brackets--;
2940                                 } else if ((vare[0] == '$') && (vare[1] == '['))
2941                                         needsub++;
2942                                 vare++;
2943                         }
2944                         if (brackets)
2945                                 ast_log(LOG_WARNING, "Error in extension logic (missing '}')\n");
2946                         len = vare - vars - 1;
2947
2948                         /* Skip totally over variable string */
2949                         whereweare += (len + 3);
2950
2951                         if (!var)
2952                                 var = alloca(VAR_BUF_SIZE);
2953
2954                         /* Store variable name (and truncate) */
2955                         ast_copy_string(var, vars, len + 1);
2956
2957                         /* Substitute if necessary */
2958                         if (needsub) {
2959                                 if (!ltmp)
2960                                         ltmp = alloca(VAR_BUF_SIZE);
2961
2962                                 pbx_substitute_variables_helper_full(c, headp, var, ltmp, VAR_BUF_SIZE - 1);
2963                                 vars = ltmp;
2964                         } else {
2965                                 vars = var;
2966                         }
2967
2968                         if (!workspace)
2969                                 workspace = alloca(VAR_BUF_SIZE);
2970
2971                         workspace[0] = '\0';
2972
2973                         parse_variable_name(vars, &offset, &offset2, &isfunction);
2974                         if (isfunction) {
2975                                 /* Evaluate function */
2976                                 if (c || !headp)
2977                                         cp4 = ast_func_read(c, vars, workspace, VAR_BUF_SIZE) ? NULL : workspace;
2978                                 else {
2979                                         struct varshead old;
2980                                         struct ast_channel *c = ast_channel_alloc(0, 0, "", "", "", "", "", 0, "Bogus/%p", vars);
2981                                         if (c) {
2982                                                 memcpy(&old, &c->varshead, sizeof(old));
2983                                                 memcpy(&c->varshead, headp, sizeof(c->varshead));
2984                                                 cp4 = ast_func_read(c, vars, workspace, VAR_BUF_SIZE) ? NULL : workspace;
2985                                                 /* Don't deallocate the varshead that was passed in */
2986                                                 memcpy(&c->varshead, &old, sizeof(c->varshead));
2987                                                 ast_channel_free(c);
2988                                         } else
2989                                                 ast_log(LOG_ERROR, "Unable to allocate bogus channel for variable substitution.  Function results may be blank.\n");
2990                                 }
2991                                 ast_debug(2, "Function result is '%s'\n", cp4 ? cp4 : "(null)");
2992                         } else {
2993                                 /* Retrieve variable value */
2994                                 pbx_retrieve_variable(c, vars, &cp4, workspace, VAR_BUF_SIZE, headp);
2995                         }
2996                         if (cp4) {
2997                                 cp4 = substring(cp4, offset, offset2, workspace, VAR_BUF_SIZE);
2998
2999        &n