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