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