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