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