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, struct match_char *current, char *pattern, int is_pattern, int already, int specificity, struct match_char **parent);
960 static void create_match_char_tree(struct ast_context *con);
961 static struct ast_exten *get_canmatch_exten(struct match_char *node);
962 static void destroy_pattern_tree(struct match_char *pattern_tree);
963 int ast_hashtab_compare_contexts(const void *ah_a, const void *ah_b);
964 static int hashtab_compare_extens(const void *ha_a, const void *ah_b);
965 static int hashtab_compare_exten_numbers(const void *ah_a, const void *ah_b);
966 static int hashtab_compare_exten_labels(const void *ah_a, const void *ah_b);
967 unsigned int ast_hashtab_hash_contexts(const void *obj);
968 static unsigned int hashtab_hash_extens(const void *obj);
969 static unsigned int hashtab_hash_priority(const void *obj);
970 static unsigned int hashtab_hash_labels(const void *obj);
971 static void __ast_internal_context_destroy( struct ast_context *con);
972
973 /* a func for qsort to use to sort a char array */
974 static int compare_char(const void *a, const void *b)
975 {
976         const char *ac = a;
977         const char *bc = b;
978         if ((*ac) < (*bc))
979                 return -1;
980         else if ((*ac) == (*bc))
981                 return 0;
982         else
983                 return 1;
984 }
985
986 /* labels, contexts are case sensitive  priority numbers are ints */
987 int ast_hashtab_compare_contexts(const void *ah_a, const void *ah_b)
988 {
989         const struct ast_context *ac = ah_a;
990         const struct ast_context *bc = ah_b;
991         if (!ac || !bc) /* safety valve, but it might prevent a crash you'd rather have happen */
992                 return 1;
993         /* assume context names are registered in a string table! */
994         return strcmp(ac->name, bc->name);
995 }
996
997 static int hashtab_compare_extens(const void *ah_a, const void *ah_b)
998 {
999         const struct ast_exten *ac = ah_a;
1000         const struct ast_exten *bc = ah_b;
1001         int x = strcmp(ac->exten, bc->exten);
1002         if (x) { /* if exten names are diff, then return */
1003                 return x;
1004         }
1005         
1006         /* but if they are the same, do the cidmatch values match? */
1007         if (ac->matchcid && bc->matchcid) {
1008                 return strcmp(ac->cidmatch,bc->cidmatch);
1009         } else if (!ac->matchcid && !bc->matchcid) {
1010                 return 0; /* if there's no matchcid on either side, then this is a match */
1011         } else {
1012                 return 1; /* if there's matchcid on one but not the other, they are different */
1013         }
1014 }
1015
1016 static int hashtab_compare_exten_numbers(const void *ah_a, const void *ah_b)
1017 {
1018         const struct ast_exten *ac = ah_a;
1019         const struct ast_exten *bc = ah_b;
1020         return ac->priority != bc->priority;
1021 }
1022
1023 static int hashtab_compare_exten_labels(const void *ah_a, const void *ah_b)
1024 {
1025         const struct ast_exten *ac = ah_a;
1026         const struct ast_exten *bc = ah_b;
1027         return strcmp(ac->label, bc->label);
1028 }
1029
1030 unsigned int ast_hashtab_hash_contexts(const void *obj)
1031 {
1032         const struct ast_context *ac = obj;
1033         return ast_hashtab_hash_string(ac->name);
1034 }
1035
1036 static unsigned int hashtab_hash_extens(const void *obj)
1037 {
1038         const struct ast_exten *ac = obj;
1039         unsigned int x = ast_hashtab_hash_string(ac->exten);
1040         unsigned int y = 0;
1041         if (ac->matchcid)
1042                 y = ast_hashtab_hash_string(ac->cidmatch);
1043         return x+y;
1044 }
1045
1046 static unsigned int hashtab_hash_priority(const void *obj)
1047 {
1048         const struct ast_exten *ac = obj;
1049         return ast_hashtab_hash_int(ac->priority);
1050 }
1051
1052 static unsigned int hashtab_hash_labels(const void *obj)
1053 {
1054         const struct ast_exten *ac = obj;
1055         return ast_hashtab_hash_string(ac->label);
1056 }
1057
1058
1059 AST_RWLOCK_DEFINE_STATIC(globalslock);
1060 static struct varshead globals = AST_LIST_HEAD_NOLOCK_INIT_VALUE;
1061
1062 static int autofallthrough = 1;
1063 static int extenpatternmatchnew = 0;
1064 static char *overrideswitch = NULL;
1065
1066 /*! \brief Subscription for device state change events */
1067 static struct ast_event_sub *device_state_sub;
1068
1069 AST_MUTEX_DEFINE_STATIC(maxcalllock);
1070 static int countcalls;
1071 static int totalcalls;
1072
1073 static AST_RWLIST_HEAD_STATIC(acf_root, ast_custom_function);
1074
1075 /*! \brief Declaration of builtin applications */
1076 static struct pbx_builtin {
1077         char name[AST_MAX_APP];
1078         int (*execute)(struct ast_channel *chan, void *data);
1079 } builtins[] =
1080 {
1081         /* These applications are built into the PBX core and do not
1082            need separate modules */
1083
1084         { "Answer",         pbx_builtin_answer },
1085         { "BackGround",     pbx_builtin_background },
1086         { "Busy",           pbx_builtin_busy },
1087         { "Congestion",     pbx_builtin_congestion },
1088         { "ExecIfTime",     pbx_builtin_execiftime },
1089         { "Goto",           pbx_builtin_goto },
1090         { "GotoIf",         pbx_builtin_gotoif },
1091         { "GotoIfTime",     pbx_builtin_gotoiftime },
1092         { "ImportVar",      pbx_builtin_importvar },
1093         { "Hangup",         pbx_builtin_hangup },
1094         { "Incomplete",     pbx_builtin_incomplete },
1095         { "KeepAlive",      pbx_builtin_keepalive },
1096         { "NoOp",           pbx_builtin_noop },
1097         { "Proceeding",     pbx_builtin_proceeding },
1098         { "Progress",       pbx_builtin_progress },
1099         { "RaiseException", pbx_builtin_raise_exception },
1100         { "ResetCDR",       pbx_builtin_resetcdr },
1101         { "Ringing",        pbx_builtin_ringing },
1102         { "SayAlpha",       pbx_builtin_saycharacters },
1103         { "SayDigits",      pbx_builtin_saydigits },
1104         { "SayNumber",      pbx_builtin_saynumber },
1105         { "SayPhonetic",    pbx_builtin_sayphonetic },
1106         { "Set",            pbx_builtin_setvar },
1107         { "MSet",           pbx_builtin_setvar_multiple },
1108         { "SetAMAFlags",    pbx_builtin_setamaflags },
1109         { "Wait",           pbx_builtin_wait },
1110         { "WaitExten",      pbx_builtin_waitexten }
1111 };
1112
1113 static struct ast_context *contexts;
1114 static struct ast_hashtab *contexts_table = NULL;
1115
1116 AST_RWLOCK_DEFINE_STATIC(conlock);              /*!< Lock for the ast_context list */
1117
1118 static AST_RWLIST_HEAD_STATIC(apps, ast_app);
1119
1120 static AST_RWLIST_HEAD_STATIC(switches, ast_switch);
1121
1122 static int stateid = 1;
1123 /* WARNING:
1124    When holding this list's lock, do _not_ do anything that will cause conlock
1125    to be taken, unless you _already_ hold it. The ast_merge_contexts_and_delete
1126    function will take the locks in conlock/hints order, so any other
1127    paths that require both locks must also take them in that order.
1128 */
1129 static AST_RWLIST_HEAD_STATIC(hints, ast_hint);
1130
1131 static AST_LIST_HEAD_NOLOCK_STATIC(statecbs, ast_state_cb);
1132
1133 #ifdef CONTEXT_DEBUG
1134
1135 /* these routines are provided for doing run-time checks
1136    on the extension structures, in case you are having
1137    problems, this routine might help you localize where
1138    the problem is occurring. It's kinda like a debug memory
1139    allocator's arena checker... It'll eat up your cpu cycles!
1140    but you'll see, if you call it in the right places,
1141    right where your problems began...
1142 */
1143
1144 /* you can break on the check_contexts_trouble()
1145 routine in your debugger to stop at the moment
1146 there's a problem */
1147 void check_contexts_trouble(void);
1148
1149 void check_contexts_trouble(void)
1150 {
1151         int x = 1;
1152         x = 2;
1153 }
1154
1155 static struct ast_context *find_context_locked(const char *context);
1156 int check_contexts(char *, int);
1157
1158 int check_contexts(char *file, int line )
1159 {
1160         struct ast_hashtab_iter *t1;
1161         struct ast_context *c1, *c2;
1162         int found = 0;
1163         struct ast_exten *e1, *e2, *e3;
1164         struct ast_exten ex;
1165         
1166         /* try to find inconsistencies */
1167         /* is every context in the context table in the context list and vice-versa ? */
1168         
1169         if (!contexts_table) {
1170                 ast_log(LOG_NOTICE,"Called from: %s:%d: No contexts_table!\n", file, line);
1171                 usleep(500000);
1172         }
1173
1174         t1 = ast_hashtab_start_traversal(contexts_table);
1175         while( (c1 = ast_hashtab_next(t1))) {
1176                 for(c2=contexts;c2;c2=c2->next) {
1177                         if (!strcmp(c1->name, c2->name)) {
1178                                 found = 1;
1179                                 break;
1180                         }
1181                 }
1182                 if (!found) {
1183                         ast_log(LOG_NOTICE,"Called from: %s:%d: Could not find the %s context in the linked list\n", file, line, c1->name);
1184                         check_contexts_trouble();
1185                 }
1186         }
1187         ast_hashtab_end_traversal(t1);
1188         for(c2=contexts;c2;c2=c2->next) {
1189                 c1 = find_context_locked(c2->name);
1190                 if (!c1) {
1191                         ast_log(LOG_NOTICE,"Called from: %s:%d: Could not find the %s context in the hashtab\n", file, line, c2->name);
1192                         check_contexts_trouble();
1193                 } else
1194                         ast_unlock_contexts();
1195         }
1196
1197         /* loop thru all contexts, and verify the exten structure compares to the 
1198            hashtab structure */
1199         for(c2=contexts;c2;c2=c2->next) {
1200                 c1 = find_context_locked(c2->name);
1201                 if (c1)
1202                 {
1203
1204                         ast_unlock_contexts();
1205
1206                         /* is every entry in the root list also in the root_table? */
1207                         for(e1 = c1->root; e1; e1=e1->next)
1208                         {
1209                                 char dummy_name[1024];
1210                                 ex.exten = dummy_name;
1211                                 ex.matchcid = e1->matchcid;
1212                                 ex.cidmatch = e1->cidmatch;
1213                                 ast_copy_string(dummy_name, e1->exten, sizeof(dummy_name));
1214                                 e2 = ast_hashtab_lookup(c1->root_table, &ex);
1215                                 if (!e2) {
1216                                         if (e1->matchcid) {
1217                                                 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 );
1218                                         } else {
1219                                                 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 );
1220                                         }
1221                                         check_contexts_trouble();
1222                                 }
1223                         }
1224                         
1225                         /* is every entry in the root_table also in the root list? */ 
1226                         if (!c2->root_table) {
1227                                 if (c2->root) {
1228                                         ast_log(LOG_NOTICE,"Called from: %s:%d: No c2->root_table for context %s!\n", file, line, c2->name);
1229                                         usleep(500000);
1230                                 }
1231                         } else {
1232                                 t1 = ast_hashtab_start_traversal(c2->root_table);
1233                                 while( (e2 = ast_hashtab_next(t1)) ) {
1234                                         for(e1=c2->root;e1;e1=e1->next) {
1235                                                 if (!strcmp(e1->exten, e2->exten)) {
1236                                                         found = 1;
1237                                                         break;
1238                                                 }
1239                                         }
1240                                         if (!found) {
1241                                                 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);
1242                                                 check_contexts_trouble();
1243                                         }
1244                                         
1245                                 }
1246                                 ast_hashtab_end_traversal(t1);
1247                         }
1248                 }
1249                 /* is every priority reflected in the peer_table at the head of the list? */
1250                 
1251                 /* is every entry in the root list also in the root_table? */
1252                 /* are the per-extension peer_tables in the right place? */
1253
1254                 for(e1 = c2->root; e1; e1 = e1->next) {
1255                         
1256                         for(e2=e1;e2;e2=e2->peer) {
1257                                 ex.priority = e2->priority;
1258                                 if (e2 != e1 && e2->peer_table) {
1259                                         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 );
1260                                         check_contexts_trouble();
1261                                 }
1262                                 
1263                                 if (e2 != e1 && e2->peer_label_table) {
1264                                         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 );
1265                                         check_contexts_trouble();
1266                                 }
1267                                 
1268                                 if (e2 == e1 && !e2->peer_table){
1269                                         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 );
1270                                         check_contexts_trouble();
1271                                 }
1272                                 
1273                                 if (e2 == e1 && !e2->peer_label_table) {
1274                                         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 );
1275                                         check_contexts_trouble();
1276                                 }
1277                                 
1278
1279                                 e3 = ast_hashtab_lookup(e1->peer_table, &ex);
1280                                 if (!e3) {
1281                                         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 );
1282                                         check_contexts_trouble();
1283                                 }
1284                         }
1285                         
1286                         if (!e1->peer_table){
1287                                 ast_log(LOG_NOTICE,"Called from: %s:%d: No e1->peer_table!\n", file, line);
1288                                 usleep(500000);
1289                         }
1290                         
1291                         /* is every entry in the peer_table also in the peer list? */ 
1292                         t1 = ast_hashtab_start_traversal(e1->peer_table);
1293                         while( (e2 = ast_hashtab_next(t1)) ) {
1294                                 for(e3=e1;e3;e3=e3->peer) {
1295                                         if (e3->priority == e2->priority) {
1296                                                 found = 1;
1297                                                 break;
1298                                         }
1299                                 }
1300                                 if (!found) {
1301                                         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 );
1302                                         check_contexts_trouble();
1303                                 }
1304                         }
1305                         ast_hashtab_end_traversal(t1);
1306                 }
1307         }
1308         return 0;
1309 }
1310 #endif
1311
1312 /*
1313    \note This function is special. It saves the stack so that no matter
1314    how many times it is called, it returns to the same place */
1315 int pbx_exec(struct ast_channel *c,             /*!< Channel */
1316              struct ast_app *app,               /*!< Application */
1317              void *data)                        /*!< Data for execution */
1318 {
1319         int res;
1320         struct ast_module_user *u = NULL;
1321         const char *saved_c_appl;
1322         const char *saved_c_data;
1323
1324         if (c->cdr && !ast_check_hangup(c))
1325                 ast_cdr_setapp(c->cdr, app->name, data);
1326
1327         /* save channel values */
1328         saved_c_appl= c->appl;
1329         saved_c_data= c->data;
1330
1331         c->appl = app->name;
1332         c->data = data;
1333         if (app->module)
1334                 u = __ast_module_user_add(app->module, c);
1335         res = app->execute(c, S_OR(data, ""));
1336         if (app->module && u)
1337                 __ast_module_user_remove(app->module, u);
1338         /* restore channel values */
1339         c->appl = saved_c_appl;
1340         c->data = saved_c_data;
1341         return res;
1342 }
1343
1344
1345 /*! Go no deeper than this through includes (not counting loops) */
1346 #define AST_PBX_MAX_STACK       128
1347
1348 /*! \brief Find application handle in linked list
1349  */
1350 struct ast_app *pbx_findapp(const char *app)
1351 {
1352         struct ast_app *tmp;
1353
1354         AST_RWLIST_RDLOCK(&apps);
1355         AST_RWLIST_TRAVERSE(&apps, tmp, list) {
1356                 if (!strcasecmp(tmp->name, app))
1357                         break;
1358         }
1359         AST_RWLIST_UNLOCK(&apps);
1360
1361         return tmp;
1362 }
1363
1364 static struct ast_switch *pbx_findswitch(const char *sw)
1365 {
1366         struct ast_switch *asw;
1367
1368         AST_RWLIST_RDLOCK(&switches);
1369         AST_RWLIST_TRAVERSE(&switches, asw, list) {
1370                 if (!strcasecmp(asw->name, sw))
1371                         break;
1372         }
1373         AST_RWLIST_UNLOCK(&switches);
1374
1375         return asw;
1376 }
1377
1378 static inline int include_valid(struct ast_include *i)
1379 {
1380         if (!i->hastime)
1381                 return 1;
1382
1383         return ast_check_timing(&(i->timing));
1384 }
1385
1386 static void pbx_destroy(struct ast_pbx *p)
1387 {
1388         ast_free(p);
1389 }
1390
1391 /* form a tree that fully describes all the patterns in a context's extensions 
1392  * in this tree, a "node" represents an individual character or character set
1393  * meant to match the corresponding character in a dial string. The tree 
1394  * consists of a series of match_char structs linked in a chain
1395  * via the alt_char pointers. More than one pattern can share the same parts of the 
1396  * tree as other extensions with the same pattern to that point. 
1397  * My first attempt to duplicate the finding of the 'best' pattern was flawed in that
1398  * I misunderstood the general algorithm. I thought that the 'best' pattern
1399  * was the one with lowest total score. This was not true. Thus, if you have
1400  * patterns "1XXXXX" and "X11111", you would be tempted to say that "X11111" is
1401  * the "best" match because it has fewer X's, and is therefore more specific, 
1402  * but this is not how the old algorithm works. It sorts matching patterns
1403  * in a similar collating sequence as sorting alphabetic strings, from left to 
1404  * right. Thus, "1XXXXX" comes before "X11111", and would be the "better" match,
1405  * because "1" is more specific than "X".
1406  * So, to accomodate this philosophy, I sort the tree branches along the alt_char
1407  * line so they are lowest to highest in specificity numbers. This way, as soon
1408  * as we encounter our first complete match, we automatically have the "best" 
1409  * match and can stop the traversal immediately. Same for CANMATCH/MATCHMORE.
1410  * If anyone would like to resurrect the "wrong" pattern trie searching algorithm,
1411  * they are welcome to revert pbx to before 1 Apr 2008.
1412  * As an example, consider these 4 extensions:
1413  * (a) NXXNXXXXXX
1414  * (b) 307754XXXX 
1415  * (c) fax
1416  * (d) NXXXXXXXXX
1417  *
1418  * In the above, between (a) and (d), (a) is a more specific pattern than (d), and would win over
1419  * most numbers. For all numbers beginning with 307754, (b) should always win.
1420  *
1421  * These pattern should form a (sorted) tree that looks like this:
1422  *   { "3" }  --next-->  { "0" }  --next--> { "7" } --next--> { "7" } --next--> { "5" } ... blah ... --> { "X" exten_match: (b) }
1423  *      |
1424  *      |alt
1425  *      |
1426  *   { "f" }  --next-->  { "a" }  --next--> { "x"  exten_match: (c) }
1427  *   { "N" }  --next-->  { "X" }  --next--> { "X" } --next--> { "N" } --next--> { "X" } ... blah ... --> { "X" exten_match: (a) }
1428  *      |                                                        |
1429  *      |                                                        |alt
1430  *      |alt                                                     |
1431  *      |                                                     { "X" } --next--> { "X" } ... blah ... --> { "X" exten_match: (d) }
1432  *      |
1433  *     NULL
1434  *
1435  *   In the above, I could easily turn "N" into "23456789", but I think that a quick "if( *z >= '2' && *z <= '9' )" might take
1436  *   fewer CPU cycles than a call to strchr("23456789",*z), where *z is the char to match...
1437  *
1438  *   traversal is pretty simple: one routine merely traverses the alt list, and for each matching char in the pattern,  it calls itself
1439  *   on the corresponding next pointer, incrementing also the pointer of the string to be matched, and passing the total specificity and length.
1440  *   We pass a pointer to a scoreboard down through, also.
1441  *   The scoreboard isn't as necessary to the revised algorithm, but I kept it as a handy way to return the matched extension.
1442  *   The first complete match ends the traversal, which should make this version of the pattern matcher faster
1443  *   the previous. The same goes for "CANMATCH" or "MATCHMORE"; the first such match ends the traversal. In both
1444  *   these cases, the reason we can stop immediately, is because the first pattern match found will be the "best"
1445  *   according to the sort criteria.
1446  *   Hope the limit on stack depth won't be a problem... this routine should 
1447  *   be pretty lean as far a stack usage goes. Any non-match terminates the recursion down a branch.
1448  *
1449  *   In the above example, with the number "3077549999" as the pattern, the traversor could match extensions a, b and d.  All are
1450  *   of length 10; they have total specificities of  24580, 10246, and 25090, respectively, not that this matters
1451  *   at all. (b) wins purely because the first character "3" is much more specific (lower specificity) than "N". I have
1452  *   left the specificity totals in the code as an artifact; at some point, I will strip it out.
1453  *
1454  *   Just how much time this algorithm might save over a plain linear traversal over all possible patterns is unknown,
1455  *   because it's a function of how many extensions are stored in a context. With thousands of extensions, the speedup
1456  *   can be very noticeable. The new matching algorithm can run several hundreds of times faster, if not a thousand or
1457  *   more times faster in extreme cases.
1458  *
1459  *   MatchCID patterns are also supported, and stored in the tree just as the extension pattern is. Thus, you
1460  *   can have patterns in your CID field as well.
1461  *
1462  * */
1463
1464
1465 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)
1466 {
1467         /* if this extension is marked as deleted, then skip this -- if it never shows
1468            on the scoreboard, it will never be found, nor will halt the traversal. */
1469         if (deleted)
1470                 return;
1471         board->total_specificity = spec;
1472         board->total_length = length;
1473         board->exten = exten;
1474         board->last_char = last;
1475         board->node = node;
1476 #ifdef NEED_DEBUG_HERE
1477         ast_log(LOG_NOTICE,"Scoreboarding (LONGER) %s, len=%d, score=%d\n", exten->exten, length, spec);
1478 #endif
1479 }
1480
1481 void log_match_char_tree(struct match_char *node, char *prefix)
1482 {
1483         char extenstr[40];
1484         struct ast_str *my_prefix = ast_str_alloca(1024); 
1485
1486         extenstr[0] = '\0';
1487
1488         if (node && node->exten && node->exten)
1489                 snprintf(extenstr, sizeof(extenstr), "(%p)", node->exten);
1490         
1491         if (strlen(node->x) > 1) {
1492                 ast_debug(1, "%s[%s]:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y':'N', 
1493                         node->deleted? 'D':'-', node->specificity, node->exten? "EXTEN:":"", 
1494                         node->exten ? node->exten->exten : "", extenstr);
1495         } else {
1496                 ast_debug(1, "%s%s:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y':'N', 
1497                         node->deleted? 'D':'-', node->specificity, node->exten? "EXTEN:":"", 
1498                         node->exten ? node->exten->exten : "", extenstr);
1499         }
1500
1501         ast_str_set(&my_prefix, 0, "%s+       ", prefix);
1502
1503         if (node->next_char)
1504                 log_match_char_tree(node->next_char, my_prefix->str);
1505
1506         if (node->alt_char)
1507                 log_match_char_tree(node->alt_char, prefix);
1508 }
1509
1510 static void cli_match_char_tree(struct match_char *node, char *prefix, int fd)
1511 {
1512         char extenstr[40];
1513         struct ast_str *my_prefix = ast_str_alloca(1024);
1514         
1515         extenstr[0] = '\0';
1516
1517         if (node && node->exten && node->exten)
1518                 snprintf(extenstr, sizeof(extenstr), "(%p)", node->exten);
1519         
1520         if (strlen(node->x) > 1) {
1521                 ast_cli(fd, "%s[%s]:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y' : 'N', 
1522                         node->deleted ? 'D' : '-', node->specificity, node->exten? "EXTEN:" : "", 
1523                         node->exten ? node->exten->exten : "", extenstr);
1524         } else {
1525                 ast_cli(fd, "%s%s:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y' : 'N', 
1526                         node->deleted ? 'D' : '-', node->specificity, node->exten? "EXTEN:" : "", 
1527                         node->exten ? node->exten->exten : "", extenstr);
1528         }
1529
1530         ast_str_set(&my_prefix, 0, "%s+       ", prefix);
1531
1532         if (node->next_char)
1533                 cli_match_char_tree(node->next_char, my_prefix->str, fd);
1534
1535         if (node->alt_char)
1536                 cli_match_char_tree(node->alt_char, prefix, fd);
1537 }
1538
1539 static struct ast_exten *get_canmatch_exten(struct match_char *node)
1540 {
1541         /* find the exten at the end of the rope */
1542         struct match_char *node2 = node;
1543
1544         for (node2 = node; node2; node2 = node2->next_char) {
1545                 if (node2->exten) {
1546 #ifdef NEED_DEBUG_HERE
1547                         ast_log(LOG_NOTICE,"CanMatch_exten returns exten %s(%p)\n", node2->exten->exten, node2->exten);
1548 #endif
1549                         return node2->exten;
1550                 }
1551         }
1552 #ifdef NEED_DEBUG_HERE
1553         ast_log(LOG_NOTICE,"CanMatch_exten returns NULL, match_char=%s\n", node->x);
1554 #endif
1555         return 0;
1556 }
1557
1558 static struct ast_exten *trie_find_next_match(struct match_char *node)
1559 {
1560         struct match_char *m3;
1561         struct match_char *m4;
1562         struct ast_exten *e3;
1563         
1564         if (node && node->x[0] == '.' && !node->x[1]) /* dot and ! will ALWAYS be next match in a matchmore */
1565                 return node->exten;
1566         
1567         if (node && node->x[0] == '!' && !node->x[1])
1568                 return node->exten;
1569         
1570         if (!node || !node->next_char)
1571                 return NULL;
1572         
1573         m3 = node->next_char;
1574
1575         if (m3->exten)
1576                 return m3->exten;
1577         for(m4=m3->alt_char; m4; m4 = m4->alt_char) {
1578                 if (m4->exten)
1579                         return m4->exten;
1580         }
1581         for(m4=m3; m4; m4 = m4->alt_char) {
1582                 e3 = trie_find_next_match(m3);
1583                 if (e3)
1584                         return e3;
1585         }
1586         return NULL;
1587 }
1588
1589 #ifdef DEBUG_THIS
1590 static char *action2str(enum ext_match_t action)
1591 {
1592         switch(action)
1593         {
1594         case E_MATCH:
1595                 return "MATCH";
1596         case E_CANMATCH:
1597                 return "CANMATCH";
1598         case E_MATCHMORE:
1599                 return "MATCHMORE";
1600         case E_FINDLABEL:
1601                 return "FINDLABEL";
1602         case E_SPAWN:
1603                 return "SPAWN";
1604         default:
1605                 return "?ACTION?";
1606         }
1607 }
1608
1609 #endif
1610
1611 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)
1612 {
1613         struct match_char *p; /* note minimal stack storage requirements */
1614         struct ast_exten pattern = { .label = label };
1615 #ifdef DEBUG_THIS
1616         if (tree)
1617                 ast_log(LOG_NOTICE,"new_find_extension called with %s on (sub)tree %s action=%s\n", str, tree->x, action2str(action));
1618         else
1619                 ast_log(LOG_NOTICE,"new_find_extension called with %s on (sub)tree NULL action=%s\n", str, action2str(action));
1620 #endif
1621         for (p=tree; p; p=p->alt_char) {
1622                 if (p->x[0] == 'N') {
1623                         if (p->x[1] == 0 && *str >= '2' && *str <= '9' ) {
1624 #define NEW_MATCHER_CHK_MATCH          \
1625                                 if (p->exten && !(*(str+1))) { /* if a shorter pattern matches along the way, might as well report it */             \
1626                                         if (action == E_MATCH || action == E_SPAWN || action == E_FINDLABEL) { /* if in CANMATCH/MATCHMORE, don't let matches get in the way */   \
1627                                                 update_scoreboard(score, length+1, spec+p->specificity, p->exten,0,callerid, p->deleted, p);                 \
1628                                                 if (!p->deleted) {                                                                                           \
1629                                                         if (action == E_FINDLABEL) {                                                                             \
1630                                                                 if (ast_hashtab_lookup(score->exten->peer_label_table, &pattern)) {                                  \
1631                                                                         ast_debug(4, "Found label in preferred extension\n");                                            \
1632                                                                         return;                                                                                          \
1633                                                                 }                                                                                                    \
1634                                                         } else {                                                                                                 \
1635                                                                 ast_debug(4,"returning an exact match-- first found-- %s\n", p->exten->exten);                       \
1636                                                                 return; /* the first match, by definition, will be the best, because of the sorted tree */           \
1637                                                         }                                                                                                        \
1638                                                 }                                                                                                            \
1639                                         }                                                                                                                \
1640                                 }
1641                                 
1642 #define NEW_MATCHER_RECURSE                \
1643                                 if (p->next_char && ( *(str+1) || (p->next_char->x[0] == '/' && p->next_char->x[1] == 0)                 \
1644                                                || p->next_char->x[0] == '!')) {                                          \
1645                                         if (*(str+1) || p->next_char->x[0] == '!') {                                                         \
1646                                                 new_find_extension(str+1, score, p->next_char, length+1, spec+p->specificity, callerid, label, action); \
1647                                                 if (score->exten)  {                                                                             \
1648                                                 ast_debug(4,"returning an exact match-- %s\n", score->exten->exten);                         \
1649                                                         return; /* the first match is all we need */                                                 \
1650                                                 }                                                                                                                                                \
1651                                         } else {                                                                                             \
1652                                                 new_find_extension("/", score, p->next_char, length+1, spec+p->specificity, callerid, label, action);    \
1653                                                 if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {      \
1654                                                 ast_debug(4,"returning a (can/more) match--- %s\n", score->exten ? score->exten->exten :     \
1655                                        "NULL");                                                                        \
1656                                                         return; /* the first match is all we need */                                                 \
1657                                                 }                                                                                                                                                \
1658                                         }                                                                                                    \
1659                                 } else if (p->next_char && !*(str+1)) {                                                                  \
1660                                         score->canmatch = 1;                                                                                 \
1661                                         score->canmatch_exten = get_canmatch_exten(p);                                                       \
1662                                         if (action == E_CANMATCH || action == E_MATCHMORE) {                                                 \
1663                                         ast_debug(4,"returning a canmatch/matchmore--- str=%s\n", str);                                  \
1664                                                 return;                                                                                          \
1665                                         }                                                                                                                                                    \
1666                                 }
1667                                 
1668                                 NEW_MATCHER_CHK_MATCH;
1669                                 NEW_MATCHER_RECURSE;
1670                         }
1671                 } else if (p->x[0] == 'Z') {
1672                         if (p->x[1] == 0 && *str >= '1' && *str <= '9' ) {
1673                                 NEW_MATCHER_CHK_MATCH;
1674                                 NEW_MATCHER_RECURSE;
1675                         }
1676                 } else if (p->x[0] == 'X') { 
1677                         if (p->x[1] == 0 && *str >= '0' && *str <= '9' ) {
1678                                 NEW_MATCHER_CHK_MATCH;
1679                                 NEW_MATCHER_RECURSE;
1680                         }
1681                 } else if (p->x[0] == '.' && p->x[1] == 0) {
1682                         /* how many chars will the . match against? */
1683                         int i = 0;
1684                         const char *str2 = str;
1685                         while (*str2 && *str2 != '/') {
1686                                 str2++;
1687                                 i++;
1688                         }
1689                         if (p->exten && *str2 != '/') {
1690                                 update_scoreboard(score, length+i, spec+(i*p->specificity), p->exten, '.', callerid, p->deleted, p);
1691                                 if (score->exten) {
1692                                         ast_debug(4,"return because scoreboard has a match with '/'--- %s\n", score->exten->exten);
1693                                         return; /* the first match is all we need */
1694                                 }
1695                         }
1696                         if (p->next_char && p->next_char->x[0] == '/' && p->next_char->x[1] == 0) {
1697                                 new_find_extension("/", score, p->next_char, length+i, spec+(p->specificity*i), callerid, label, action);
1698                                 if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
1699                                         ast_debug(4,"return because scoreboard has exact match OR CANMATCH/MATCHMORE & canmatch set--- %s\n", score->exten ? score->exten->exten : "NULL");
1700                                         return; /* the first match is all we need */
1701                                 }
1702                         }
1703                 } else if (p->x[0] == '!' && p->x[1] == 0) {
1704                         /* how many chars will the . match against? */
1705                         int i = 1;
1706                         const char *str2 = str;
1707                         while (*str2 && *str2 != '/') {
1708                                 str2++;
1709                                 i++;
1710                         }
1711                         if (p->exten && *str2 != '/') {
1712                                 update_scoreboard(score, length+1, spec+(p->specificity*i), p->exten, '!', callerid, p->deleted, p);
1713                                 if (score->exten) {
1714                                         ast_debug(4,"return because scoreboard has a '!' match--- %s\n", score->exten->exten);
1715                                         return; /* the first match is all we need */
1716                                 }
1717                         }
1718                         if (p->next_char && p->next_char->x[0] == '/' && p->next_char->x[1] == 0) {
1719                                 new_find_extension("/", score, p->next_char, length+i, spec+(p->specificity*i), callerid, label, action);
1720                                 if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
1721                                         ast_debug(4,"return because scoreboard has exact match OR CANMATCH/MATCHMORE & canmatch set with '/' and '!'--- %s\n", score->exten ? score->exten->exten : "NULL");
1722                                         return; /* the first match is all we need */
1723                                 }
1724                         }
1725                 } else if (p->x[0] == '/' && p->x[1] == 0) {
1726                         /* the pattern in the tree includes the cid match! */
1727                         if (p->next_char && callerid && *callerid) {
1728                                 new_find_extension(callerid, score, p->next_char, length+1, spec, callerid, label, action);
1729                                 if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
1730                                         ast_debug(4,"return because scoreboard has exact match OR CANMATCH/MATCHMORE & canmatch set with '/'--- %s\n", score->exten ? score->exten->exten : "NULL");
1731                                         return; /* the first match is all we need */
1732                                 }
1733                         }
1734                 } else if (strchr(p->x, *str)) {
1735                         ast_debug(4, "Nothing strange about this match\n");
1736                         NEW_MATCHER_CHK_MATCH;
1737                         NEW_MATCHER_RECURSE;
1738                 }
1739         }
1740         ast_debug(4,"return at end of func\n");
1741 }
1742
1743 /* the algorithm for forming the extension pattern tree is also a bit simple; you 
1744  * traverse all the extensions in a context, and for each char of the extension,
1745  * you see if it exists in the tree; if it doesn't, you add it at the appropriate
1746  * spot. What more can I say? At the end of each exten, you cap it off by adding the
1747  * address of the extension involved. Duplicate patterns will be complained about.
1748  *
1749  * Ideally, this would be done for each context after it is created and fully 
1750  * filled. It could be done as a finishing step after extensions.conf or .ael is
1751  * loaded, or it could be done when the first search is encountered. It should only
1752  * have to be done once, until the next unload or reload.
1753  *
1754  * I guess forming this pattern tree would be analogous to compiling a regex. Except
1755  * that a regex only handles 1 pattern, really. This trie holds any number
1756  * of patterns. Well, really, it **could** be considered a single pattern,
1757  * where the "|" (or) operator is allowed, I guess, in a way, sort of...
1758  */
1759
1760 static struct match_char *already_in_tree(struct match_char *current, char *pat)
1761 {
1762         struct match_char *t;
1763
1764         if (!current)
1765                 return 0;
1766
1767         for (t = current; t; t = t->alt_char) {
1768                 if (!strcmp(pat, t->x)) /* uh, we may want to sort exploded [] contents to make matching easy */
1769                         return t;
1770         }
1771
1772         return 0;
1773 }
1774
1775 /* The first arg is the location of the tree ptr, or the 
1776    address of the next_char ptr in the node, so we can mess
1777    with it, if we need to insert at the beginning of the list */
1778
1779 static void insert_in_next_chars_alt_char_list(struct match_char **parent_ptr, struct match_char *node)
1780 {
1781         struct match_char *curr, *lcurr;
1782         
1783         /* insert node into the tree at "current", so the alt_char list from current is
1784            sorted in increasing value as you go to the leaves */
1785         if (!(*parent_ptr)) {
1786                 *parent_ptr = node;
1787         } else {
1788                 if ((*parent_ptr)->specificity > node->specificity){
1789                         /* insert at head */
1790                         node->alt_char = (*parent_ptr);
1791                         *parent_ptr = node;
1792                 } else {
1793                         lcurr = *parent_ptr;
1794                         for (curr=(*parent_ptr)->alt_char; curr; curr = curr->alt_char) {
1795                                 if (curr->specificity > node->specificity) {
1796                                         node->alt_char = curr;
1797                                         lcurr->alt_char = node;
1798                                         break;
1799                                 }
1800                                 lcurr = curr;
1801                         }
1802                         if (!curr) {
1803                                 lcurr->alt_char = node;
1804                         }
1805                 }
1806         }
1807 }
1808
1809
1810
1811 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)
1812 {
1813         struct match_char *m;
1814         
1815         if (!(m = ast_calloc(1, sizeof(*m))))
1816                 return NULL;
1817
1818         if (!(m->x = ast_strdup(pattern))) {
1819                 ast_free(m);
1820                 return NULL;
1821         }
1822
1823         /* the specificity scores are the same as used in the old
1824            pattern matcher. */
1825         m->is_pattern = is_pattern;
1826         if (specificity == 1 && is_pattern && pattern[0] == 'N')
1827                 m->specificity = 0x0802;
1828         else if (specificity == 1 && is_pattern && pattern[0] == 'Z')
1829                 m->specificity = 0x0901;
1830         else if (specificity == 1 && is_pattern && pattern[0] == 'X')
1831                 m->specificity = 0x0a00;
1832         else if (specificity == 1 && is_pattern && pattern[0] == '.')
1833                 m->specificity = 0x10000;
1834         else if (specificity == 1 && is_pattern && pattern[0] == '!')
1835                 m->specificity = 0x20000;
1836         else
1837                 m->specificity = specificity;
1838         
1839         if (!con->pattern_tree) {
1840                 insert_in_next_chars_alt_char_list(&con->pattern_tree, m);
1841         } else {
1842                 if (already) { /* switch to the new regime (traversing vs appending)*/
1843                         insert_in_next_chars_alt_char_list(nextcharptr, m);
1844                 } else {
1845                         insert_in_next_chars_alt_char_list(&current->next_char, m);
1846                 }
1847         }
1848
1849         return m;
1850 }
1851
1852 static struct match_char *add_exten_to_pattern_tree(struct ast_context *con, struct ast_exten *e1, int findonly)
1853 {
1854         struct match_char *m1 = NULL, *m2 = NULL, **m0;
1855         int specif;
1856         int already;
1857         int pattern = 0;
1858         char buf[256];
1859         char extenbuf[512];
1860         char *s1 = extenbuf;
1861         int l1 = strlen(e1->exten) + strlen(e1->cidmatch) + 2;
1862         
1863
1864         strncpy(extenbuf,e1->exten,sizeof(extenbuf));
1865         if (e1->matchcid &&  l1 <= sizeof(extenbuf)) {
1866                 strcat(extenbuf,"/");
1867                 strcat(extenbuf,e1->cidmatch);
1868         } else if (l1 > sizeof(extenbuf)) {
1869                 ast_log(LOG_ERROR,"The pattern %s/%s is too big to deal with: it will be ignored! Disaster!\n", e1->exten, e1->cidmatch);
1870                 return 0;
1871         }
1872 #ifdef NEED_DEBUG
1873         ast_log(LOG_DEBUG,"Adding exten %s%c%s to tree\n", s1, e1->matchcid? '/':' ', e1->matchcid? e1->cidmatch : "");
1874 #endif
1875         m1 = con->pattern_tree; /* each pattern starts over at the root of the pattern tree */
1876         m0 = &con->pattern_tree;
1877         already = 1;
1878
1879         if ( *s1 == '_') {
1880                 pattern = 1;
1881                 s1++;
1882         }
1883         while( *s1 ) {
1884                 if (pattern && *s1 == '[' && *(s1-1) != '\\') {
1885                         char *s2 = buf;
1886                         buf[0] = 0;
1887                         s1++; /* get past the '[' */
1888                         while (*s1 != ']' && *(s1-1) != '\\' ) {
1889                                 if (*s1 == '\\') {
1890                                         if (*(s1+1) == ']') {
1891                                                 *s2++ = ']';
1892                                                 s1++;s1++;
1893                                         } else if (*(s1+1) == '\\') {
1894                                                 *s2++ = '\\';
1895                                                 s1++;s1++;
1896                                         } else if (*(s1+1) == '-') {
1897                                                 *s2++ = '-';
1898                                                 s1++; s1++;
1899                                         } else if (*(s1+1) == '[') {
1900                                                 *s2++ = '[';
1901                                                 s1++; s1++;
1902                                         }
1903                                 } else if (*s1 == '-') { /* remember to add some error checking to all this! */
1904                                         char s3 = *(s1-1);
1905                                         char s4 = *(s1+1);
1906                                         for (s3++; s3 <= s4; s3++) {
1907                                                 *s2++ = s3;
1908                                         }
1909                                         s1++; s1++;
1910                                 } else {
1911                                         *s2++ = *s1++;
1912                                 }
1913                         }
1914                         *s2 = 0; /* null terminate the exploded range */
1915                         /* sort the characters */
1916
1917                         specif = strlen(buf);
1918                         qsort(buf, specif, 1, compare_char);
1919                         specif <<= 8;
1920                         specif += buf[0];
1921                 } else {
1922                         
1923                         if (*s1 == '\\') {
1924                                 s1++;
1925                                 buf[0] = *s1;
1926                         } else {
1927                                 if (pattern) {
1928                                         if (*s1 == 'n') /* make sure n,x,z patterns are canonicalized to N,X,Z */
1929                                                 *s1 = 'N';
1930                                         else if (*s1 == 'x')
1931                                                 *s1 = 'X';
1932                                         else if (*s1 == 'z')
1933                                                 *s1 = 'Z';
1934                                 }
1935                                 buf[0] = *s1;
1936                         }
1937                         buf[1] = 0;
1938                         specif = 1;
1939                 }
1940                 m2 = 0;
1941                 if (already && (m2=already_in_tree(m1,buf)) && m2->next_char) {
1942                         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...
1943                                                                 a shorter pattern might win if the longer one doesn't match */
1944                                 m2->exten = e1;
1945                                 m2->deleted = 0;
1946                         }
1947                         m1 = m2->next_char; /* m1 points to the node to compare against */
1948                         m0 = &m2->next_char; /* m0 points to the ptr that points to m1 */
1949                 } else { /* not already OR not m2 OR nor m2->next_char */
1950                         if (m2) {
1951                                 if (findonly)
1952                                         return m2;
1953                                 m1 = m2; /* while m0 stays the same */
1954                         } else {
1955                                 if (findonly)
1956                                         return m1;
1957                                 m1 = add_pattern_node(con, m1, buf, pattern, already,specif, m0); /* m1 is the node just added */
1958                                 m0 = &m1->next_char;
1959                         }
1960                         
1961                         if (!(*(s1+1))) {
1962                                 m1->deleted = 0;
1963                                 m1->exten = e1;
1964                         }
1965                         
1966                         already = 0;
1967                 }
1968                 s1++; /* advance to next char */
1969         }
1970         return m1;
1971 }
1972
1973 static void create_match_char_tree(struct ast_context *con)
1974 {
1975         struct ast_hashtab_iter *t1;
1976         struct ast_exten *e1;
1977 #ifdef NEED_DEBUG
1978         int biggest_bucket, resizes, numobjs, numbucks;
1979         
1980         ast_log(LOG_DEBUG,"Creating Extension Trie for context %s\n", con->name);
1981         ast_hashtab_get_stats(con->root_table, &biggest_bucket, &resizes, &numobjs, &numbucks);
1982         ast_log(LOG_DEBUG,"This tree has %d objects in %d bucket lists, longest list=%d objects, and has resized %d times\n",
1983                         numobjs, numbucks, biggest_bucket, resizes);
1984 #endif
1985         t1 = ast_hashtab_start_traversal(con->root_table);
1986         while( (e1 = ast_hashtab_next(t1)) ) {
1987                 if (e1->exten)
1988                         add_exten_to_pattern_tree(con, e1, 0);
1989                 else
1990                         ast_log(LOG_ERROR,"Attempt to create extension with no extension name.\n");
1991         }
1992         ast_hashtab_end_traversal(t1);
1993 }
1994
1995 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! */
1996 {
1997         /* destroy all the alternates */
1998         if (pattern_tree->alt_char) {
1999                 destroy_pattern_tree(pattern_tree->alt_char);
2000                 pattern_tree->alt_char = 0;
2001         }
2002         /* destroy all the nexts */
2003         if (pattern_tree->next_char) {
2004                 destroy_pattern_tree(pattern_tree->next_char);
2005                 pattern_tree->next_char = 0;
2006         }
2007         pattern_tree->exten = 0; /* never hurts to make sure there's no pointers laying around */
2008         if (pattern_tree->x)
2009                 free(pattern_tree->x);
2010         free(pattern_tree);
2011 }
2012
2013 /*
2014  * Special characters used in patterns:
2015  *      '_'     underscore is the leading character of a pattern.
2016  *              In other position it is treated as a regular char.
2017  *      ' ' '-' space and '-' are separator and ignored.
2018  *      .       one or more of any character. Only allowed at the end of
2019  *              a pattern.
2020  *      !       zero or more of anything. Also impacts the result of CANMATCH
2021  *              and MATCHMORE. Only allowed at the end of a pattern.
2022  *              In the core routine, ! causes a match with a return code of 2.
2023  *              In turn, depending on the search mode: (XXX check if it is implemented)
2024  *              - E_MATCH retuns 1 (does match)
2025  *              - E_MATCHMORE returns 0 (no match)
2026  *              - E_CANMATCH returns 1 (does match)
2027  *
2028  *      /       should not appear as it is considered the separator of the CID info.
2029  *              XXX at the moment we may stop on this char.
2030  *
2031  *      X Z N   match ranges 0-9, 1-9, 2-9 respectively.
2032  *      [       denotes the start of a set of character. Everything inside
2033  *              is considered literally. We can have ranges a-d and individual
2034  *              characters. A '[' and '-' can be considered literally if they
2035  *              are just before ']'.
2036  *              XXX currently there is no way to specify ']' in a range, nor \ is
2037  *              considered specially.
2038  *
2039  * When we compare a pattern with a specific extension, all characters in the extension
2040  * itself are considered literally with the only exception of '-' which is considered
2041  * as a separator and thus ignored.
2042  * XXX do we want to consider space as a separator as well ?
2043  * XXX do we want to consider the separators in non-patterns as well ?
2044  */
2045
2046 /*!
2047  * \brief helper functions to sort extensions and patterns in the desired way,
2048  * so that more specific patterns appear first.
2049  *
2050  * ext_cmp1 compares individual characters (or sets of), returning
2051  * an int where bits 0-7 are the ASCII code of the first char in the set,
2052  * while bit 8-15 are the cardinality of the set minus 1.
2053  * This way more specific patterns (smaller cardinality) appear first.
2054  * Wildcards have a special value, so that we can directly compare them to
2055  * sets by subtracting the two values. In particular:
2056  *      0x000xx         one character, xx
2057  *      0x0yyxx         yy character set starting with xx
2058  *      0x10000         '.' (one or more of anything)
2059  *      0x20000         '!' (zero or more of anything)
2060  *      0x30000         NUL (end of string)
2061  *      0x40000         error in set.
2062  * The pointer to the string is advanced according to needs.
2063  * NOTES:
2064  *      1. the empty set is equivalent to NUL.
2065  *      2. given that a full set has always 0 as the first element,
2066  *         we could encode the special cases as 0xffXX where XX
2067  *         is 1, 2, 3, 4 as used above.
2068  */
2069 static int ext_cmp1(const char **p)
2070 {
2071         uint32_t chars[8];
2072         int c, cmin = 0xff, count = 0;
2073         const char *end;
2074
2075         /* load, sign extend and advance pointer until we find
2076          * a valid character.
2077          */
2078         while ( (c = *(*p)++) && (c == ' ' || c == '-') )
2079                 ;       /* ignore some characters */
2080
2081         /* always return unless we have a set of chars */
2082         switch (toupper(c)) {
2083         default:        /* ordinary character */
2084                 return 0x0000 | (c & 0xff);
2085
2086         case 'N':       /* 2..9 */
2087                 return 0x0800 | '2' ;
2088
2089         case 'X':       /* 0..9 */
2090                 return 0x0A00 | '0';
2091
2092         case 'Z':       /* 1..9 */
2093                 return 0x0900 | '1';
2094
2095         case '.':       /* wildcard */
2096                 return 0x10000;
2097
2098         case '!':       /* earlymatch */
2099                 return 0x20000; /* less specific than NULL */
2100
2101         case '\0':      /* empty string */
2102                 *p = NULL;
2103                 return 0x30000;
2104
2105         case '[':       /* pattern */
2106                 break;
2107         }
2108         /* locate end of set */
2109         end = strchr(*p, ']');  
2110
2111         if (end == NULL) {
2112                 ast_log(LOG_WARNING, "Wrong usage of [] in the extension\n");
2113                 return 0x40000; /* XXX make this entry go last... */
2114         }
2115
2116         memset(chars, '\0', sizeof(chars));     /* clear all chars in the set */
2117         for (; *p < end  ; (*p)++) {
2118                 unsigned char c1, c2;   /* first-last char in range */
2119                 c1 = (unsigned char)((*p)[0]);
2120                 if (*p + 2 < end && (*p)[1] == '-') { /* this is a range */
2121                         c2 = (unsigned char)((*p)[2]);
2122                         *p += 2;        /* skip a total of 3 chars */
2123                 } else                  /* individual character */
2124                         c2 = c1;
2125                 if (c1 < cmin)
2126                         cmin = c1;
2127                 for (; c1 <= c2; c1++) {
2128                         uint32_t mask = 1 << (c1 % 32);
2129                         if ( (chars[ c1 / 32 ] & mask) == 0)
2130                                 count += 0x100;
2131                         chars[ c1 / 32 ] |= mask;
2132                 }
2133         }
2134         (*p)++;
2135         return count == 0 ? 0x30000 : (count | cmin);
2136 }
2137
2138 /*!
2139  * \brief the full routine to compare extensions in rules.
2140  */
2141 static int ext_cmp(const char *a, const char *b)
2142 {
2143         /* make sure non-patterns come first.
2144          * If a is not a pattern, it either comes first or
2145          * we use strcmp to compare the strings.
2146          */
2147         int ret = 0;
2148
2149         if (a[0] != '_')
2150                 return (b[0] == '_') ? -1 : strcmp(a, b);
2151
2152         /* Now we know a is a pattern; if b is not, a comes first */
2153         if (b[0] != '_')
2154                 return 1;
2155 #if 0   /* old mode for ext matching */
2156         return strcmp(a, b);
2157 #endif
2158         /* ok we need full pattern sorting routine */
2159         while (!ret && a && b)
2160                 ret = ext_cmp1(&a) - ext_cmp1(&b);
2161         if (ret == 0)
2162                 return 0;
2163         else
2164                 return (ret > 0) ? 1 : -1;
2165 }
2166
2167 int ast_extension_cmp(const char *a, const char *b)
2168 {
2169         return ext_cmp(a, b);
2170 }
2171
2172 /*!
2173  * \internal
2174  * \brief used ast_extension_{match|close}
2175  * mode is as follows:
2176  *      E_MATCH         success only on exact match
2177  *      E_MATCHMORE     success only on partial match (i.e. leftover digits in pattern)
2178  *      E_CANMATCH      either of the above.
2179  * \retval 0 on no-match
2180  * \retval 1 on match
2181  * \retval 2 on early match.
2182  */
2183
2184 static int _extension_match_core(const char *pattern, const char *data, enum ext_match_t mode)
2185 {
2186         mode &= E_MATCH_MASK;   /* only consider the relevant bits */
2187         
2188 #ifdef NEED_DEBUG_HERE
2189         ast_log(LOG_NOTICE,"match core: pat: '%s', dat: '%s', mode=%d\n", pattern, data, (int)mode);
2190 #endif
2191         
2192         if ( (mode == E_MATCH) && (pattern[0] == '_') && (!strcasecmp(pattern,data)) ) { /* note: if this test is left out, then _x. will not match _x. !!! */
2193 #ifdef NEED_DEBUG_HERE
2194                 ast_log(LOG_NOTICE,"return (1) - pattern matches pattern\n");
2195 #endif
2196                 return 1;
2197         }
2198
2199         if (pattern[0] != '_') { /* not a pattern, try exact or partial match */
2200                 int ld = strlen(data), lp = strlen(pattern);
2201                 
2202                 if (lp < ld) {          /* pattern too short, cannot match */
2203 #ifdef NEED_DEBUG_HERE
2204                         ast_log(LOG_NOTICE,"return (0) - pattern too short, cannot match\n");
2205 #endif
2206                         return 0;
2207                 }
2208                 /* depending on the mode, accept full or partial match or both */
2209                 if (mode == E_MATCH) {
2210 #ifdef NEED_DEBUG_HERE
2211                         ast_log(LOG_NOTICE,"return (!strcmp(%s,%s) when mode== E_MATCH)\n", pattern, data);
2212 #endif
2213                         return !strcmp(pattern, data); /* 1 on match, 0 on fail */
2214                 } 
2215                 if (ld == 0 || !strncasecmp(pattern, data, ld)) { /* partial or full match */
2216 #ifdef NEED_DEBUG_HERE
2217                         ast_log(LOG_NOTICE,"return (mode(%d) == E_MATCHMORE ? lp(%d) > ld(%d) : 1)\n", mode, lp, ld);
2218 #endif
2219                         return (mode == E_MATCHMORE) ? lp > ld : 1; /* XXX should consider '!' and '/' ? */
2220                 } else {
2221 #ifdef NEED_DEBUG_HERE
2222                         ast_log(LOG_NOTICE,"return (0) when ld(%d) > 0 && pattern(%s) != data(%s)\n", ld, pattern, data);
2223 #endif
2224                         return 0;
2225                 }
2226         }
2227         pattern++; /* skip leading _ */
2228         /*
2229          * XXX below we stop at '/' which is a separator for the CID info. However we should
2230          * not store '/' in the pattern at all. When we insure it, we can remove the checks.
2231          */
2232         while (*data && *pattern && *pattern != '/') {
2233                 const char *end;
2234
2235                 if (*data == '-') { /* skip '-' in data (just a separator) */
2236                         data++;
2237                         continue;
2238                 }
2239                 switch (toupper(*pattern)) {
2240                 case '[':       /* a range */
2241                         end = strchr(pattern+1, ']'); /* XXX should deal with escapes ? */
2242                         if (end == NULL) {
2243                                 ast_log(LOG_WARNING, "Wrong usage of [] in the extension\n");
2244                                 return 0;       /* unconditional failure */
2245                         }
2246                         for (pattern++; pattern != end; pattern++) {
2247                                 if (pattern+2 < end && pattern[1] == '-') { /* this is a range */
2248                                         if (*data >= pattern[0] && *data <= pattern[2])
2249                                                 break;  /* match found */
2250                                         else {
2251                                                 pattern += 2; /* skip a total of 3 chars */
2252                                                 continue;
2253                                         }
2254                                 } else if (*data == pattern[0])
2255                                         break;  /* match found */
2256                         }
2257                         if (pattern == end) {
2258 #ifdef NEED_DEBUG_HERE
2259                                 ast_log(LOG_NOTICE,"return (0) when pattern==end\n");
2260 #endif
2261                                 return 0;
2262                         }
2263                         pattern = end;  /* skip and continue */
2264                         break;
2265                 case 'N':
2266                         if (*data < '2' || *data > '9') {
2267 #ifdef NEED_DEBUG_HERE
2268                                 ast_log(LOG_NOTICE,"return (0) N is matched\n");
2269 #endif
2270                                 return 0;
2271                         }
2272                         break;
2273                 case 'X':
2274                         if (*data < '0' || *data > '9') {
2275 #ifdef NEED_DEBUG_HERE
2276                                 ast_log(LOG_NOTICE,"return (0) X is matched\n");
2277 #endif
2278                                 return 0;
2279                         }
2280                         break;
2281                 case 'Z':
2282                         if (*data < '1' || *data > '9') {
2283 #ifdef NEED_DEBUG_HERE
2284                                 ast_log(LOG_NOTICE,"return (0) Z is matched\n");
2285 #endif
2286                                 return 0;
2287                         }
2288                         break;
2289                 case '.':       /* Must match, even with more digits */
2290 #ifdef NEED_DEBUG_HERE
2291                         ast_log(LOG_NOTICE,"return (1) when '.' is matched\n");
2292 #endif
2293                         return 1;
2294                 case '!':       /* Early match */
2295 #ifdef NEED_DEBUG_HERE
2296                         ast_log(LOG_NOTICE,"return (2) when '!' is matched\n");
2297 #endif
2298                         return 2;
2299                 case ' ':
2300                 case '-':       /* Ignore these in patterns */
2301                         data--; /* compensate the final data++ */
2302                         break;
2303                 default:
2304                         if (*data != *pattern) {
2305 #ifdef NEED_DEBUG_HERE
2306                                 ast_log(LOG_NOTICE,"return (0) when *data(%c) != *pattern(%c)\n", *data, *pattern);
2307 #endif
2308                                 return 0;
2309                         }
2310                         
2311                 }
2312                 data++;
2313                 pattern++;
2314         }
2315         if (*data)                      /* data longer than pattern, no match */ {
2316 #ifdef NEED_DEBUG_HERE
2317                 ast_log(LOG_NOTICE,"return (0) when data longer than pattern\n");
2318 #endif
2319                 return 0;
2320         }
2321         
2322         /*
2323          * match so far, but ran off the end of the data.
2324          * Depending on what is next, determine match or not.
2325          */
2326         if (*pattern == '\0' || *pattern == '/') {      /* exact match */
2327 #ifdef NEED_DEBUG_HERE
2328                 ast_log(LOG_NOTICE,"at end, return (%d) in 'exact match'\n", (mode==E_MATCHMORE) ? 0 : 1);
2329 #endif
2330                 return (mode == E_MATCHMORE) ? 0 : 1;   /* this is a failure for E_MATCHMORE */
2331         } else if (*pattern == '!')     {               /* early match */
2332 #ifdef NEED_DEBUG_HERE
2333                 ast_log(LOG_NOTICE,"at end, return (2) when '!' is matched\n");
2334 #endif
2335                 return 2;
2336         } else {                                                /* partial match */
2337 #ifdef NEED_DEBUG_HERE
2338                 ast_log(LOG_NOTICE,"at end, return (%d) which deps on E_MATCH\n", (mode == E_MATCH) ? 0 : 1);
2339 #endif
2340                 return (mode == E_MATCH) ? 0 : 1;       /* this is a failure for E_MATCH */
2341         }
2342 }
2343
2344 /*
2345  * Wrapper around _extension_match_core() to do performance measurement
2346  * using the profiling code.
2347  */
2348 static int extension_match_core(const char *pattern, const char *data, enum ext_match_t mode)
2349 {
2350         int i;
2351         static int prof_id = -2;        /* marker for 'unallocated' id */
2352         if (prof_id == -2)
2353                 prof_id = ast_add_profile("ext_match", 0);
2354         ast_mark(prof_id, 1);
2355         i = _extension_match_core(pattern, data, mode);
2356         ast_mark(prof_id, 0);
2357         return i;
2358 }
2359
2360 int ast_extension_match(const char *pattern, const char *data)
2361 {
2362         return extension_match_core(pattern, data, E_MATCH);
2363 }
2364
2365 int ast_extension_close(const char *pattern, const char *data, int needmore)
2366 {
2367         if (needmore != E_MATCHMORE && needmore != E_CANMATCH)
2368                 ast_log(LOG_WARNING, "invalid argument %d\n", needmore);
2369         return extension_match_core(pattern, data, needmore);
2370 }
2371
2372 struct fake_context /* this struct is purely for matching in the hashtab */
2373 {
2374         ast_rwlock_t lock;                      
2375         struct ast_exten *root;         
2376         struct ast_hashtab *root_table;            
2377         struct match_char *pattern_tree;       
2378         struct ast_context *next;       
2379         struct ast_include *includes;           
2380         struct ast_ignorepat *ignorepats;       
2381         const char *registrar;
2382         int refcount;
2383         AST_LIST_HEAD_NOLOCK(, ast_sw) alts;    
2384         ast_mutex_t macrolock;          
2385         char name[256];         
2386 };
2387
2388 struct ast_context *ast_context_find(const char *name)
2389 {
2390         struct ast_context *tmp = NULL;
2391         struct fake_context item;
2392         strncpy(item.name,name,256);
2393         ast_rdlock_contexts();
2394         if( contexts_table ) {
2395                 tmp = ast_hashtab_lookup(contexts_table,&item);
2396         } else {
2397                 while ( (tmp = ast_walk_contexts(tmp)) ) {
2398                         if (!name || !strcasecmp(name, tmp->name))
2399                                 break;
2400                 }
2401         }
2402         ast_unlock_contexts();
2403         return tmp;
2404 }
2405
2406 #define STATUS_NO_CONTEXT       1
2407 #define STATUS_NO_EXTENSION     2
2408 #define STATUS_NO_PRIORITY      3
2409 #define STATUS_NO_LABEL         4
2410 #define STATUS_SUCCESS          5
2411
2412 static int matchcid(const char *cidpattern, const char *callerid)
2413 {
2414         /* If the Caller*ID pattern is empty, then we're matching NO Caller*ID, so
2415            failing to get a number should count as a match, otherwise not */
2416
2417         if (ast_strlen_zero(callerid))
2418                 return ast_strlen_zero(cidpattern) ? 1 : 0;
2419
2420         return ast_extension_match(cidpattern, callerid);
2421 }
2422
2423 struct ast_exten *pbx_find_extension(struct ast_channel *chan,
2424         struct ast_context *bypass, struct pbx_find_info *q,
2425         const char *context, const char *exten, int priority,
2426         const char *label, const char *callerid, enum ext_match_t action)
2427 {
2428         int x, res;
2429         struct ast_context *tmp = NULL;
2430         struct ast_exten *e = NULL, *eroot = NULL;
2431         struct ast_include *i = NULL;
2432         struct ast_sw *sw = NULL;
2433         struct ast_exten pattern = {NULL, };
2434         struct scoreboard score = {0, };
2435         struct ast_str *tmpdata = NULL;
2436
2437         pattern.label = label;
2438         pattern.priority = priority;
2439 #ifdef NEED_DEBUG_HERE
2440         ast_log(LOG_NOTICE,"Looking for cont/ext/prio/label/action = %s/%s/%d/%s/%d\n", context, exten, priority, label, (int)action);
2441 #endif
2442
2443         /* Initialize status if appropriate */
2444         if (q->stacklen == 0) {
2445                 q->status = STATUS_NO_CONTEXT;
2446                 q->swo = NULL;
2447                 q->data = NULL;
2448                 q->foundcontext = NULL;
2449         } else if (q->stacklen >= AST_PBX_MAX_STACK) {
2450                 ast_log(LOG_WARNING, "Maximum PBX stack exceeded\n");
2451                 return NULL;
2452         }
2453
2454         /* Check first to see if we've already been checked */
2455         for (x = 0; x < q->stacklen; x++) {
2456                 if (!strcasecmp(q->incstack[x], context))
2457                         return NULL;
2458         }
2459
2460         if (bypass)     /* bypass means we only look there */
2461                 tmp = bypass;
2462         else {  /* look in contexts */
2463                 struct fake_context item;
2464                 strncpy(item.name,context,256);
2465                 tmp = ast_hashtab_lookup(contexts_table,&item);
2466 #ifdef NOTNOW
2467                 tmp = NULL;
2468                 while ((tmp = ast_walk_contexts(tmp)) ) {
2469                         if (!strcmp(tmp->name, context))
2470                                 break;
2471                 }
2472 #endif
2473                 if (!tmp)
2474                         return NULL;
2475                 
2476         }
2477
2478         if (q->status < STATUS_NO_EXTENSION)
2479                 q->status = STATUS_NO_EXTENSION;
2480         
2481         /* Do a search for matching extension */
2482
2483         eroot = NULL;
2484         score.total_specificity = 0;
2485         score.exten = 0;
2486         score.total_length = 0;
2487         if (!tmp->pattern_tree && tmp->root_table)
2488         {
2489                 create_match_char_tree(tmp);
2490 #ifdef NEED_DEBUG
2491                 ast_log(LOG_DEBUG,"Tree Created in context %s:\n", context);
2492                 log_match_char_tree(tmp->pattern_tree," ");
2493 #endif
2494         }
2495 #ifdef NEED_DEBUG
2496         ast_log(LOG_NOTICE,"The Trie we are searching in:\n");
2497         log_match_char_tree(tmp->pattern_tree, "::  ");
2498 #endif
2499
2500         do {
2501                 if (!ast_strlen_zero(overrideswitch)) {
2502                         char *osw = ast_strdupa(overrideswitch), *name;
2503                         struct ast_switch *asw;
2504                         ast_switch_f *aswf = NULL;
2505                         char *datap;
2506                         int eval = 0;
2507
2508                         name = strsep(&osw, "/");
2509                         asw = pbx_findswitch(name);
2510
2511                         if (!asw) {
2512                                 ast_log(LOG_WARNING, "No such switch '%s'\n", name);
2513                                 break;
2514                         }
2515
2516                         if (osw && strchr(osw, '$')) {
2517                                 eval = 1;
2518                         }
2519
2520                         if (eval && !(tmpdata = ast_str_thread_get(&switch_data, 512))) {
2521                                 ast_log(LOG_WARNING, "Can't evaluate overrideswitch?!");
2522                                 break;
2523                         } else if (eval) {
2524                                 /* Substitute variables now */
2525                                 pbx_substitute_variables_helper(chan, osw, tmpdata->str, tmpdata->len);
2526                                 datap = tmpdata->str;
2527                         } else {
2528                                 datap = osw;
2529                         }
2530
2531                         /* equivalent of extension_match_core() at the switch level */
2532                         if (action == E_CANMATCH)
2533                                 aswf = asw->canmatch;
2534                         else if (action == E_MATCHMORE)
2535                                 aswf = asw->matchmore;
2536                         else /* action == E_MATCH */
2537                                 aswf = asw->exists;
2538                         if (!aswf) {
2539                                 res = 0;
2540                         } else {
2541                                 if (chan) {
2542                                         ast_autoservice_start(chan);
2543                                 }
2544                                 res = aswf(chan, context, exten, priority, callerid, datap);
2545                                 if (chan) {
2546                                         ast_autoservice_stop(chan);
2547                                 }
2548                         }
2549                         if (res) {      /* Got a match */
2550                                 q->swo = asw;
2551                                 q->data = datap;
2552                                 q->foundcontext = context;
2553                                 /* XXX keep status = STATUS_NO_CONTEXT ? */
2554                                 return NULL;
2555                         }
2556                 }
2557         } while (0);
2558
2559         if (extenpatternmatchnew) {
2560                 new_find_extension(exten, &score, tmp->pattern_tree, 0, 0, callerid, label, action);
2561                 eroot = score.exten;
2562                 
2563                 if (score.last_char == '!' && action == E_MATCHMORE) {
2564                         /* We match an extension ending in '!'.
2565                          * The decision in this case is final and is NULL (no match).
2566                          */
2567 #ifdef NEED_DEBUG_HERE
2568                         ast_log(LOG_NOTICE,"Returning MATCHMORE NULL with exclamation point.\n");
2569 #endif
2570                         return NULL;
2571                 }
2572                 
2573                 if (!eroot && (action == E_CANMATCH || action == E_MATCHMORE) && score.canmatch_exten) {
2574                         q->status = STATUS_SUCCESS;
2575 #ifdef NEED_DEBUG_HERE
2576                         ast_log(LOG_NOTICE,"Returning CANMATCH exten %s\n", score.canmatch_exten->exten);
2577 #endif
2578                         return score.canmatch_exten;
2579                 }
2580                 
2581                 if ((action == E_MATCHMORE || action == E_CANMATCH)  && eroot) {
2582                         if (score.node) {
2583                                 struct ast_exten *z = trie_find_next_match(score.node);
2584                                 if (z) {
2585 #ifdef NEED_DEBUG_HERE
2586                                         ast_log(LOG_NOTICE,"Returning CANMATCH/MATCHMORE next_match exten %s\n", z->exten);
2587 #endif
2588                                 } else {
2589                                         if (score.canmatch_exten) {
2590 #ifdef NEED_DEBUG_HERE
2591                                                 ast_log(LOG_NOTICE,"Returning CANMATCH/MATCHMORE canmatchmatch exten %s(%p)\n", score.canmatch_exten->exten, score.canmatch_exten);
2592 #endif
2593                                                 return score.canmatch_exten;
2594                                         } else {
2595 #ifdef NEED_DEBUG_HERE
2596                                                 ast_log(LOG_NOTICE,"Returning CANMATCH/MATCHMORE next_match exten NULL\n");
2597 #endif
2598                                         }
2599                                 }
2600                                 return z;
2601                         }
2602 #ifdef NEED_DEBUG_HERE
2603                         ast_log(LOG_NOTICE,"Returning CANMATCH/MATCHMORE NULL (no next_match)\n");
2604 #endif
2605                         return NULL;  /* according to the code, complete matches are null matches in MATCHMORE mode */
2606                 }
2607                 
2608                 if (eroot) {
2609                         /* found entry, now look for the right priority */
2610                         if (q->status < STATUS_NO_PRIORITY)
2611                                 q->status = STATUS_NO_PRIORITY;
2612                         e = NULL;
2613                         if (action == E_FINDLABEL && label ) {
2614                                 if (q->status < STATUS_NO_LABEL)
2615                                         q->status = STATUS_NO_LABEL;
2616                                 e = ast_hashtab_lookup(eroot->peer_label_table, &pattern);
2617                         } else {
2618                                 e = ast_hashtab_lookup(eroot->peer_table, &pattern);
2619                         }
2620                         if (e) {        /* found a valid match */
2621                                 q->status = STATUS_SUCCESS;
2622                                 q->foundcontext = context;
2623 #ifdef NEED_DEBUG_HERE
2624                                 ast_log(LOG_NOTICE,"Returning complete match of exten %s\n", e->exten);
2625 #endif
2626                                 return e;
2627                         }
2628                 }
2629         } else {   /* the old/current default exten pattern match algorithm */
2630                 
2631                 /* scan the list trying to match extension and CID */
2632                 eroot = NULL;
2633                 while ( (eroot = ast_walk_context_extensions(tmp, eroot)) ) {
2634                         int match = extension_match_core(eroot->exten, exten, action);
2635                         /* 0 on fail, 1 on match, 2 on earlymatch */
2636                         
2637                         if (!match || (eroot->matchcid && !matchcid(eroot->cidmatch, callerid)))
2638                                 continue;       /* keep trying */
2639                         if (match == 2 && action == E_MATCHMORE) {
2640                                 /* We match an extension ending in '!'.
2641                                  * The decision in this case is final and is NULL (no match).
2642                                  */
2643                                 return NULL;
2644                         }
2645                         /* found entry, now look for the right priority */
2646                         if (q->status < STATUS_NO_PRIORITY)
2647                                 q->status = STATUS_NO_PRIORITY;
2648                         e = NULL;
2649                         if (action == E_FINDLABEL && label ) {
2650                                 if (q->status < STATUS_NO_LABEL)
2651                                         q->status = STATUS_NO_LABEL;
2652                                 e = ast_hashtab_lookup(eroot->peer_label_table, &pattern);
2653                         } else {
2654                                 e = ast_hashtab_lookup(eroot->peer_table, &pattern);
2655                         }
2656 #ifdef NOTNOW
2657                         while ( (e = ast_walk_extension_priorities(eroot, e)) ) {
2658                                 /* Match label or priority */
2659                                 if (action == E_FINDLABEL) {
2660                                         if (q->status < STATUS_NO_LABEL)
2661                                                 q->status = STATUS_NO_LABEL;
2662                                         if (label && e->label && !strcmp(label, e->label))
2663                                                 break;  /* found it */
2664                                 } else if (e->priority == priority) {
2665                                         break;  /* found it */
2666                                 } /* else keep searching */
2667                         }
2668 #endif
2669                         if (e) {        /* found a valid match */
2670                                 q->status = STATUS_SUCCESS;
2671                                 q->foundcontext = context;
2672                                 return e;
2673                         }
2674                 }
2675         }
2676         
2677         
2678         /* Check alternative switches */
2679         AST_LIST_TRAVERSE(&tmp->alts, sw, list) {
2680                 struct ast_switch *asw = pbx_findswitch(sw->name);
2681                 ast_switch_f *aswf = NULL;
2682                 char *datap;
2683
2684                 if (!asw) {
2685                         ast_log(LOG_WARNING, "No such switch '%s'\n", sw->name);
2686                         continue;
2687                 }
2688                 /* Substitute variables now */
2689                 
2690                 if (sw->eval) {
2691                         if (!(tmpdata = ast_str_thread_get(&switch_data, 512))) {
2692                                 ast_log(LOG_WARNING, "Can't evaluate switch?!");
2693                                 continue;
2694                         }
2695                         pbx_substitute_variables_helper(chan, sw->data, tmpdata->str, tmpdata->len);
2696                 }
2697
2698                 /* equivalent of extension_match_core() at the switch level */
2699                 if (action == E_CANMATCH)
2700                         aswf = asw->canmatch;
2701                 else if (action == E_MATCHMORE)
2702                         aswf = asw->matchmore;
2703                 else /* action == E_MATCH */
2704                         aswf = asw->exists;
2705                 datap = sw->eval ? tmpdata->str : sw->data;
2706                 if (!aswf)
2707                         res = 0;
2708                 else {
2709                         if (chan)
2710                                 ast_autoservice_start(chan);
2711                         res = aswf(chan, context, exten, priority, callerid, datap);
2712                         if (chan)
2713                                 ast_autoservice_stop(chan);
2714                 }
2715                 if (res) {      /* Got a match */
2716                         q->swo = asw;
2717                         q->data = datap;
2718                         q->foundcontext = context;
2719                         /* XXX keep status = STATUS_NO_CONTEXT ? */
2720                         return NULL;
2721                 }
2722         }
2723         q->incstack[q->stacklen++] = tmp->name; /* Setup the stack */
2724         /* Now try any includes we have in this context */
2725         for (i = tmp->includes; i; i = i->next) {
2726                 if (include_valid(i)) {
2727                         if ((e = pbx_find_extension(chan, bypass, q, i->rname, exten, priority, label, callerid, action))) {
2728 #ifdef NEED_DEBUG_HERE
2729                                 ast_log(LOG_NOTICE,"Returning recursive match of %s\n", e->exten);
2730 #endif
2731                                 return e;
2732                         }
2733                         if (q->swo)
2734                                 return NULL;
2735                 }
2736         }
2737         return NULL;
2738 }
2739
2740 /*! 
2741  * \brief extract offset:length from variable name.
2742  * \return 1 if there is a offset:length part, which is
2743  * trimmed off (values go into variables)
2744  */
2745 static int parse_variable_name(char *var, int *offset, int *length, int *isfunc)
2746 {
2747         int parens = 0;
2748
2749         *offset = 0;
2750         *length = INT_MAX;
2751         *isfunc = 0;
2752         for (; *var; var++) {
2753                 if (*var == '(') {
2754                         (*isfunc)++;
2755                         parens++;
2756                 } else if (*var == ')') {
2757                         parens--;
2758                 } else if (*var == ':' && parens == 0) {
2759                         *var++ = '\0';
2760                         sscanf(var, "%d:%d", offset, length);
2761                         return 1; /* offset:length valid */
2762                 }
2763         }
2764         return 0;
2765 }
2766
2767 /*! 
2768  *\brief takes a substring. It is ok to call with value == workspace.
2769  * \param value
2770  * \param offset < 0 means start from the end of the string and set the beginning
2771  *   to be that many characters back.
2772  * \param length is the length of the substring, a value less than 0 means to leave
2773  * that many off the end.
2774  * \param workspace
2775  * \param workspace_len
2776  * Always return a copy in workspace.
2777  */
2778 static char *substring(const char *value, int offset, int length, char *workspace, size_t workspace_len)
2779 {
2780         char *ret = workspace;
2781         int lr; /* length of the input string after the copy */
2782
2783         ast_copy_string(workspace, value, workspace_len); /* always make a copy */
2784
2785         lr = strlen(ret); /* compute length after copy, so we never go out of the workspace */
2786
2787         /* Quick check if no need to do anything */
2788         if (offset == 0 && length >= lr)        /* take the whole string */
2789                 return ret;
2790
2791         if (offset < 0) {       /* translate negative offset into positive ones */
2792                 offset = lr + offset;
2793                 if (offset < 0) /* If the negative offset was greater than the length of the string, just start at the beginning */
2794                         offset = 0;
2795         }
2796
2797         /* too large offset result in empty string so we know what to return */
2798         if (offset >= lr)
2799                 return ret + lr;        /* the final '\0' */
2800
2801         ret += offset;          /* move to the start position */
2802         if (length >= 0 && length < lr - offset)        /* truncate if necessary */
2803                 ret[length] = '\0';
2804         else if (length < 0) {
2805                 if (lr > offset - length) /* After we remove from the front and from the rear, is there anything left? */
2806                         ret[lr + length - offset] = '\0';
2807                 else
2808                         ret[0] = '\0';
2809         }
2810
2811         return ret;
2812 }
2813
2814 /*! \brief  Support for Asterisk built-in variables in the dialplan
2815
2816 \note   See also
2817         - \ref AstVar   Channel variables
2818         - \ref AstCauses The HANGUPCAUSE variable
2819  */
2820 void pbx_retrieve_variable(struct ast_channel *c, const char *var, char **ret, char *workspace, int workspacelen, struct varshead *headp)
2821 {
2822         const char not_found = '\0';
2823         char *tmpvar;
2824         const char *s;  /* the result */
2825         int offset, length;
2826         int i, need_substring;
2827         struct varshead *places[2] = { headp, &globals };       /* list of places where we may look */
2828
2829         if (c) {
2830                 ast_channel_lock(c);
2831                 places[0] = &c->varshead;
2832         }
2833         /*
2834          * Make a copy of var because parse_variable_name() modifies the string.
2835          * Then if called directly, we might need to run substring() on the result;
2836          * remember this for later in 'need_substring', 'offset' and 'length'
2837          */
2838         tmpvar = ast_strdupa(var);      /* parse_variable_name modifies the string */
2839         need_substring = parse_variable_name(tmpvar, &offset, &length, &i /* ignored */);
2840
2841         /*
2842          * Look first into predefined variables, then into variable lists.
2843          * Variable 's' points to the result, according to the following rules:
2844          * s == &not_found (set at the beginning) means that we did not find a
2845          *      matching variable and need to look into more places.
2846          * If s != &not_found, s is a valid result string as follows:
2847          * s = NULL if the variable does not have a value;
2848          *      you typically do this when looking for an unset predefined variable.
2849          * s = workspace if the result has been assembled there;
2850          *      typically done when the result is built e.g. with an snprintf(),
2851          *      so we don't need to do an additional copy.
2852          * s != workspace in case we have a string, that needs to be copied
2853          *      (the ast_copy_string is done once for all at the end).
2854          *      Typically done when the result is already available in some string.
2855          */
2856         s = &not_found; /* default value */
2857         if (c) {        /* This group requires a valid channel */
2858                 /* Names with common parts are looked up a piece at a time using strncmp. */
2859                 if (!strncmp(var, "CALL", 4)) {
2860                         if (!strncmp(var + 4, "ING", 3)) {
2861                                 if (!strcmp(var + 7, "PRES")) {                 /* CALLINGPRES */
2862                                         snprintf(workspace, workspacelen, "%d", c->cid.cid_pres);
2863                                         s = workspace;
2864                                 } else if (!strcmp(var + 7, "ANI2")) {          /* CALLINGANI2 */
2865                                         snprintf(workspace, workspacelen, "%d", c->cid.cid_ani2);
2866                                         s = workspace;
2867                                 } else if (!strcmp(var + 7, "TON")) {           /* CALLINGTON */
2868                                         snprintf(workspace, workspacelen, "%d", c->cid.cid_ton);
2869                                         s = workspace;
2870                                 } else if (!strcmp(var + 7, "TNS")) {           /* CALLINGTNS */
2871                                         snprintf(workspace, workspacelen, "%d", c->cid.cid_tns);
2872