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