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