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