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