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