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