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