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