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