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