Add some additional documentation for core AMI events
[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         /*! Callback when state changes. */
943         ast_state_cb_type change_cb;
944         /*! Callback when destroyed so any resources given by the registerer can be freed. */
945         ast_state_cb_destroy_type destroy_cb;
946         /*! \note Only used by ast_merge_contexts_and_delete */
947         AST_LIST_ENTRY(ast_state_cb) entry;
948 };
949
950 /*!
951  * \brief Structure for dial plan hints
952  *
953  * \note Hints are pointers from an extension in the dialplan to
954  * one or more devices (tech/name)
955  *
956  * See \ref AstExtState
957  */
958 struct ast_hint {
959         /*!
960          * \brief Hint extension
961          *
962          * \note
963          * Will never be NULL while the hint is in the hints container.
964          */
965         struct ast_exten *exten;
966         struct ao2_container *callbacks; /*!< Device state callback container for this extension */
967
968         /*! Dev state variables */
969         int laststate;                  /*!< Last known device state */
970
971         /*! Presence state variables */
972         int last_presence_state;     /*!< Last known presence state */
973         char *last_presence_subtype; /*!< Last known presence subtype string */
974         char *last_presence_message; /*!< Last known presence message string */
975
976         char context_name[AST_MAX_CONTEXT];/*!< Context of destroyed hint extension. */
977         char exten_name[AST_MAX_EXTENSION];/*!< Extension of destroyed hint extension. */
978 };
979
980
981 #define HINTDEVICE_DATA_LENGTH 16
982 AST_THREADSTORAGE(hintdevice_data);
983
984 /* --- Hash tables of various objects --------*/
985 #ifdef LOW_MEMORY
986 #define HASH_EXTENHINT_SIZE 17
987 #else
988 #define HASH_EXTENHINT_SIZE 563
989 #endif
990
991
992 /*! \brief Container for hint devices */
993 static struct ao2_container *hintdevices;
994
995 /*!
996  * \brief Structure for dial plan hint devices
997  * \note hintdevice is one device pointing to a hint.
998  */
999 struct ast_hintdevice {
1000         /*!
1001          * \brief Hint this hintdevice belongs to.
1002          * \note Holds a reference to the hint object.
1003          */
1004         struct ast_hint *hint;
1005         /*! Name of the hint device. */
1006         char hintdevice[1];
1007 };
1008
1009
1010 /*!
1011  * \note Using the device for hash
1012  */
1013 static int hintdevice_hash_cb(const void *obj, const int flags)
1014 {
1015         const struct ast_hintdevice *ext = obj;
1016
1017         return ast_str_case_hash(ext->hintdevice);
1018 }
1019 /*!
1020  * \note Devices on hints are not unique so no CMP_STOP is returned
1021  * Dont use ao2_find against hintdevices container cause there always
1022  * could be more than one result.
1023  */
1024 static int hintdevice_cmp_multiple(void *obj, void *arg, int flags)
1025 {
1026         struct ast_hintdevice *ext = obj, *ext2 = arg;
1027
1028         return !strcasecmp(ext->hintdevice, ext2->hintdevice) ? CMP_MATCH  : 0;
1029 }
1030
1031 /*
1032  * \details This is used with ao2_callback to remove old devices
1033  * when they are linked to the hint
1034 */
1035 static int hintdevice_remove_cb(void *deviceobj, void *arg, int flags)
1036 {
1037         struct ast_hintdevice *device = deviceobj;
1038         struct ast_hint *hint = arg;
1039
1040         return (device->hint == hint) ? CMP_MATCH : 0;
1041 }
1042
1043 static int remove_hintdevice(struct ast_hint *hint)
1044 {
1045         /* iterate through all devices and remove the devices which are linked to this hint */
1046         ao2_t_callback(hintdevices, OBJ_NODATA | OBJ_MULTIPLE | OBJ_UNLINK,
1047                 hintdevice_remove_cb, hint,
1048                 "callback to remove all devices which are linked to a hint");
1049         return 0;
1050 }
1051
1052 static char *parse_hint_device(struct ast_str *hint_args);
1053 /*!
1054  * \internal
1055  * \brief Destroy the given hintdevice object.
1056  *
1057  * \param obj Hint device to destroy.
1058  *
1059  * \return Nothing
1060  */
1061 static void hintdevice_destroy(void *obj)
1062 {
1063         struct ast_hintdevice *doomed = obj;
1064
1065         if (doomed->hint) {
1066                 ao2_ref(doomed->hint, -1);
1067                 doomed->hint = NULL;
1068         }
1069 }
1070
1071 /*! \brief add hintdevice structure and link it into the container.
1072  */
1073 static int add_hintdevice(struct ast_hint *hint, const char *devicelist)
1074 {
1075         struct ast_str *str;
1076         char *parse;
1077         char *cur;
1078         struct ast_hintdevice *device;
1079         int devicelength;
1080
1081         if (!hint || !devicelist) {
1082                 /* Trying to add garbage? Don't bother. */
1083                 return 0;
1084         }
1085         if (!(str = ast_str_thread_get(&hintdevice_data, 16))) {
1086                 return -1;
1087         }
1088         ast_str_set(&str, 0, "%s", devicelist);
1089         parse = parse_hint_device(str);
1090
1091         while ((cur = strsep(&parse, "&"))) {
1092                 devicelength = strlen(cur);
1093                 device = ao2_t_alloc(sizeof(*device) + devicelength, hintdevice_destroy,
1094                         "allocating a hintdevice structure");
1095                 if (!device) {
1096                         return -1;
1097                 }
1098                 strcpy(device->hintdevice, cur);
1099                 ao2_ref(hint, +1);
1100                 device->hint = hint;
1101                 ao2_t_link(hintdevices, device, "Linking device into hintdevice container.");
1102                 ao2_t_ref(device, -1, "hintdevice is linked so we can unref");
1103         }
1104
1105         return 0;
1106 }
1107
1108
1109 static const struct cfextension_states {
1110         int extension_state;
1111         const char * const text;
1112 } extension_states[] = {
1113         { AST_EXTENSION_NOT_INUSE,                     "Idle" },
1114         { AST_EXTENSION_INUSE,                         "InUse" },
1115         { AST_EXTENSION_BUSY,                          "Busy" },
1116         { AST_EXTENSION_UNAVAILABLE,                   "Unavailable" },
1117         { AST_EXTENSION_RINGING,                       "Ringing" },
1118         { AST_EXTENSION_INUSE | AST_EXTENSION_RINGING, "InUse&Ringing" },
1119         { AST_EXTENSION_ONHOLD,                        "Hold" },
1120         { AST_EXTENSION_INUSE | AST_EXTENSION_ONHOLD,  "InUse&Hold" }
1121 };
1122
1123 struct presencechange {
1124         char *provider;
1125         int state;
1126         char *subtype;
1127         char *message;
1128 };
1129
1130 struct statechange {
1131         AST_LIST_ENTRY(statechange) entry;
1132         char dev[0];
1133 };
1134
1135 struct pbx_exception {
1136         AST_DECLARE_STRING_FIELDS(
1137                 AST_STRING_FIELD(context);      /*!< Context associated with this exception */
1138                 AST_STRING_FIELD(exten);        /*!< Exten associated with this exception */
1139                 AST_STRING_FIELD(reason);               /*!< The exception reason */
1140         );
1141
1142         int priority;                           /*!< Priority associated with this exception */
1143 };
1144
1145 static int pbx_builtin_answer(struct ast_channel *, const char *);
1146 static int pbx_builtin_goto(struct ast_channel *, const char *);
1147 static int pbx_builtin_hangup(struct ast_channel *, const char *);
1148 static int pbx_builtin_background(struct ast_channel *, const char *);
1149 static int pbx_builtin_wait(struct ast_channel *, const char *);
1150 static int pbx_builtin_waitexten(struct ast_channel *, const char *);
1151 static int pbx_builtin_incomplete(struct ast_channel *, const char *);
1152 static int pbx_builtin_resetcdr(struct ast_channel *, const char *);
1153 static int pbx_builtin_setamaflags(struct ast_channel *, const char *);
1154 static int pbx_builtin_ringing(struct ast_channel *, const char *);
1155 static int pbx_builtin_proceeding(struct ast_channel *, const char *);
1156 static int pbx_builtin_progress(struct ast_channel *, const char *);
1157 static int pbx_builtin_congestion(struct ast_channel *, const char *);
1158 static int pbx_builtin_busy(struct ast_channel *, const char *);
1159 static int pbx_builtin_noop(struct ast_channel *, const char *);
1160 static int pbx_builtin_gotoif(struct ast_channel *, const char *);
1161 static int pbx_builtin_gotoiftime(struct ast_channel *, const char *);
1162 static int pbx_builtin_execiftime(struct ast_channel *, const char *);
1163 static int pbx_builtin_saynumber(struct ast_channel *, const char *);
1164 static int pbx_builtin_saydigits(struct ast_channel *, const char *);
1165 static int pbx_builtin_saycharacters(struct ast_channel *, const char *);
1166 static int pbx_builtin_sayphonetic(struct ast_channel *, const char *);
1167 static int matchcid(const char *cidpattern, const char *callerid);
1168 #ifdef NEED_DEBUG
1169 static void log_match_char_tree(struct match_char *node, char *prefix); /* for use anywhere */
1170 #endif
1171 static int pbx_builtin_importvar(struct ast_channel *, const char *);
1172 static void set_ext_pri(struct ast_channel *c, const char *exten, int pri);
1173 static void new_find_extension(const char *str, struct scoreboard *score,
1174                 struct match_char *tree, int length, int spec, const char *callerid,
1175                 const char *label, enum ext_match_t action);
1176 static struct match_char *already_in_tree(struct match_char *current, char *pat, int is_pattern);
1177 static struct match_char *add_exten_to_pattern_tree(struct ast_context *con,
1178                 struct ast_exten *e1, int findonly);
1179 static void create_match_char_tree(struct ast_context *con);
1180 static struct ast_exten *get_canmatch_exten(struct match_char *node);
1181 static void destroy_pattern_tree(struct match_char *pattern_tree);
1182 static int hashtab_compare_extens(const void *ha_a, const void *ah_b);
1183 static int hashtab_compare_exten_numbers(const void *ah_a, const void *ah_b);
1184 static int hashtab_compare_exten_labels(const void *ah_a, const void *ah_b);
1185 static unsigned int hashtab_hash_extens(const void *obj);
1186 static unsigned int hashtab_hash_priority(const void *obj);
1187 static unsigned int hashtab_hash_labels(const void *obj);
1188 static void __ast_internal_context_destroy( struct ast_context *con);
1189 static int ast_add_extension_nolock(const char *context, int replace, const char *extension,
1190         int priority, const char *label, const char *callerid,
1191         const char *application, void *data, void (*datad)(void *), const char *registrar);
1192 static int ast_add_extension2_lockopt(struct ast_context *con,
1193         int replace, const char *extension, int priority, const char *label, const char *callerid,
1194         const char *application, void *data, void (*datad)(void *),
1195         const char *registrar, int lock_context);
1196 static struct ast_context *find_context_locked(const char *context);
1197 static struct ast_context *find_context(const char *context);
1198
1199 /*!
1200  * \internal
1201  * \brief Character array comparison function for qsort.
1202  *
1203  * \param a Left side object.
1204  * \param b Right side object.
1205  *
1206  * \retval <0 if a < b
1207  * \retval =0 if a = b
1208  * \retval >0 if a > b
1209  */
1210 static int compare_char(const void *a, const void *b)
1211 {
1212         const unsigned char *ac = a;
1213         const unsigned char *bc = b;
1214
1215         return *ac - *bc;
1216 }
1217
1218 /* labels, contexts are case sensitive  priority numbers are ints */
1219 int ast_hashtab_compare_contexts(const void *ah_a, const void *ah_b)
1220 {
1221         const struct ast_context *ac = ah_a;
1222         const struct ast_context *bc = ah_b;
1223         if (!ac || !bc) /* safety valve, but it might prevent a crash you'd rather have happen */
1224                 return 1;
1225         /* assume context names are registered in a string table! */
1226         return strcmp(ac->name, bc->name);
1227 }
1228
1229 static int hashtab_compare_extens(const void *ah_a, const void *ah_b)
1230 {
1231         const struct ast_exten *ac = ah_a;
1232         const struct ast_exten *bc = ah_b;
1233         int x = strcmp(ac->exten, bc->exten);
1234         if (x) { /* if exten names are diff, then return */
1235                 return x;
1236         }
1237
1238         /* but if they are the same, do the cidmatch values match? */
1239         if (ac->matchcid && bc->matchcid) {
1240                 return strcmp(ac->cidmatch,bc->cidmatch);
1241         } else if (!ac->matchcid && !bc->matchcid) {
1242                 return 0; /* if there's no matchcid on either side, then this is a match */
1243         } else {
1244                 return 1; /* if there's matchcid on one but not the other, they are different */
1245         }
1246 }
1247
1248 static int hashtab_compare_exten_numbers(const void *ah_a, const void *ah_b)
1249 {
1250         const struct ast_exten *ac = ah_a;
1251         const struct ast_exten *bc = ah_b;
1252         return ac->priority != bc->priority;
1253 }
1254
1255 static int hashtab_compare_exten_labels(const void *ah_a, const void *ah_b)
1256 {
1257         const struct ast_exten *ac = ah_a;
1258         const struct ast_exten *bc = ah_b;
1259         return strcmp(S_OR(ac->label, ""), S_OR(bc->label, ""));
1260 }
1261
1262 unsigned int ast_hashtab_hash_contexts(const void *obj)
1263 {
1264         const struct ast_context *ac = obj;
1265         return ast_hashtab_hash_string(ac->name);
1266 }
1267
1268 static unsigned int hashtab_hash_extens(const void *obj)
1269 {
1270         const struct ast_exten *ac = obj;
1271         unsigned int x = ast_hashtab_hash_string(ac->exten);
1272         unsigned int y = 0;
1273         if (ac->matchcid)
1274                 y = ast_hashtab_hash_string(ac->cidmatch);
1275         return x+y;
1276 }
1277
1278 static unsigned int hashtab_hash_priority(const void *obj)
1279 {
1280         const struct ast_exten *ac = obj;
1281         return ast_hashtab_hash_int(ac->priority);
1282 }
1283
1284 static unsigned int hashtab_hash_labels(const void *obj)
1285 {
1286         const struct ast_exten *ac = obj;
1287         return ast_hashtab_hash_string(S_OR(ac->label, ""));
1288 }
1289
1290
1291 AST_RWLOCK_DEFINE_STATIC(globalslock);
1292 static struct varshead globals = AST_LIST_HEAD_NOLOCK_INIT_VALUE;
1293
1294 static int autofallthrough = 1;
1295 static int extenpatternmatchnew = 0;
1296 static char *overrideswitch = NULL;
1297
1298 /*! \brief Subscription for device state change events */
1299 static struct ast_event_sub *device_state_sub;
1300 /*! \brief Subscription for presence state change events */
1301 static struct ast_event_sub *presence_state_sub;
1302
1303 AST_MUTEX_DEFINE_STATIC(maxcalllock);
1304 static int countcalls;
1305 static int totalcalls;
1306
1307 static AST_RWLIST_HEAD_STATIC(acf_root, ast_custom_function);
1308
1309 /*! \brief Declaration of builtin applications */
1310 static struct pbx_builtin {
1311         char name[AST_MAX_APP];
1312         int (*execute)(struct ast_channel *chan, const char *data);
1313 } builtins[] =
1314 {
1315         /* These applications are built into the PBX core and do not
1316            need separate modules */
1317
1318         { "Answer",         pbx_builtin_answer },
1319         { "BackGround",     pbx_builtin_background },
1320         { "Busy",           pbx_builtin_busy },
1321         { "Congestion",     pbx_builtin_congestion },
1322         { "ExecIfTime",     pbx_builtin_execiftime },
1323         { "Goto",           pbx_builtin_goto },
1324         { "GotoIf",         pbx_builtin_gotoif },
1325         { "GotoIfTime",     pbx_builtin_gotoiftime },
1326         { "ImportVar",      pbx_builtin_importvar },
1327         { "Hangup",         pbx_builtin_hangup },
1328         { "Incomplete",     pbx_builtin_incomplete },
1329         { "NoOp",           pbx_builtin_noop },
1330         { "Proceeding",     pbx_builtin_proceeding },
1331         { "Progress",       pbx_builtin_progress },
1332         { "RaiseException", pbx_builtin_raise_exception },
1333         { "ResetCDR",       pbx_builtin_resetcdr },
1334         { "Ringing",        pbx_builtin_ringing },
1335         { "SayAlpha",       pbx_builtin_saycharacters },
1336         { "SayDigits",      pbx_builtin_saydigits },
1337         { "SayNumber",      pbx_builtin_saynumber },
1338         { "SayPhonetic",    pbx_builtin_sayphonetic },
1339         { "Set",            pbx_builtin_setvar },
1340         { "MSet",           pbx_builtin_setvar_multiple },
1341         { "SetAMAFlags",    pbx_builtin_setamaflags },
1342         { "Wait",           pbx_builtin_wait },
1343         { "WaitExten",      pbx_builtin_waitexten }
1344 };
1345
1346 static struct ast_context *contexts;
1347 static struct ast_hashtab *contexts_table = NULL;
1348
1349 /*!
1350  * \brief Lock for the ast_context list
1351  * \note
1352  * This lock MUST be recursive, or a deadlock on reload may result.  See
1353  * https://issues.asterisk.org/view.php?id=17643
1354  */
1355 AST_MUTEX_DEFINE_STATIC(conlock);
1356
1357 /*!
1358  * \brief Lock to hold off restructuring of hints by ast_merge_contexts_and_delete.
1359  */
1360 AST_MUTEX_DEFINE_STATIC(context_merge_lock);
1361
1362 static AST_RWLIST_HEAD_STATIC(apps, ast_app);
1363
1364 static AST_RWLIST_HEAD_STATIC(switches, ast_switch);
1365
1366 static int stateid = 1;
1367 /*!
1368  * \note When holding this container's lock, do _not_ do
1369  * anything that will cause conlock to be taken, unless you
1370  * _already_ hold it.  The ast_merge_contexts_and_delete function
1371  * will take the locks in conlock/hints order, so any other
1372  * paths that require both locks must also take them in that
1373  * order.
1374  */
1375 static struct ao2_container *hints;
1376
1377 static struct ao2_container *statecbs;
1378
1379 #ifdef CONTEXT_DEBUG
1380
1381 /* these routines are provided for doing run-time checks
1382    on the extension structures, in case you are having
1383    problems, this routine might help you localize where
1384    the problem is occurring. It's kinda like a debug memory
1385    allocator's arena checker... It'll eat up your cpu cycles!
1386    but you'll see, if you call it in the right places,
1387    right where your problems began...
1388 */
1389
1390 /* you can break on the check_contexts_trouble()
1391 routine in your debugger to stop at the moment
1392 there's a problem */
1393 void check_contexts_trouble(void);
1394
1395 void check_contexts_trouble(void)
1396 {
1397         int x = 1;
1398         x = 2;
1399 }
1400
1401 int check_contexts(char *, int);
1402
1403 int check_contexts(char *file, int line )
1404 {
1405         struct ast_hashtab_iter *t1;
1406         struct ast_context *c1, *c2;
1407         int found = 0;
1408         struct ast_exten *e1, *e2, *e3;
1409         struct ast_exten ex;
1410
1411         /* try to find inconsistencies */
1412         /* is every context in the context table in the context list and vice-versa ? */
1413
1414         if (!contexts_table) {
1415                 ast_log(LOG_NOTICE,"Called from: %s:%d: No contexts_table!\n", file, line);
1416                 usleep(500000);
1417         }
1418
1419         t1 = ast_hashtab_start_traversal(contexts_table);
1420         while( (c1 = ast_hashtab_next(t1))) {
1421                 for(c2=contexts;c2;c2=c2->next) {
1422                         if (!strcmp(c1->name, c2->name)) {
1423                                 found = 1;
1424                                 break;
1425                         }
1426                 }
1427                 if (!found) {
1428                         ast_log(LOG_NOTICE,"Called from: %s:%d: Could not find the %s context in the linked list\n", file, line, c1->name);
1429                         check_contexts_trouble();
1430                 }
1431         }
1432         ast_hashtab_end_traversal(t1);
1433         for(c2=contexts;c2;c2=c2->next) {
1434                 c1 = find_context_locked(c2->name);
1435                 if (!c1) {
1436                         ast_log(LOG_NOTICE,"Called from: %s:%d: Could not find the %s context in the hashtab\n", file, line, c2->name);
1437                         check_contexts_trouble();
1438                 } else
1439                         ast_unlock_contexts();
1440         }
1441
1442         /* loop thru all contexts, and verify the exten structure compares to the
1443            hashtab structure */
1444         for(c2=contexts;c2;c2=c2->next) {
1445                 c1 = find_context_locked(c2->name);
1446                 if (c1) {
1447                         ast_unlock_contexts();
1448
1449                         /* is every entry in the root list also in the root_table? */
1450                         for(e1 = c1->root; e1; e1=e1->next)
1451                         {
1452                                 char dummy_name[1024];
1453                                 ex.exten = dummy_name;
1454                                 ex.matchcid = e1->matchcid;
1455                                 ex.cidmatch = e1->cidmatch;
1456                                 ast_copy_string(dummy_name, e1->exten, sizeof(dummy_name));
1457                                 e2 = ast_hashtab_lookup(c1->root_table, &ex);
1458                                 if (!e2) {
1459                                         if (e1->matchcid) {
1460                                                 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 );
1461                                         } else {
1462                                                 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 );
1463                                         }
1464                                         check_contexts_trouble();
1465                                 }
1466                         }
1467
1468                         /* is every entry in the root_table also in the root list? */
1469                         if (!c2->root_table) {
1470                                 if (c2->root) {
1471                                         ast_log(LOG_NOTICE,"Called from: %s:%d: No c2->root_table for context %s!\n", file, line, c2->name);
1472                                         usleep(500000);
1473                                 }
1474                         } else {
1475                                 t1 = ast_hashtab_start_traversal(c2->root_table);
1476                                 while( (e2 = ast_hashtab_next(t1)) ) {
1477                                         for(e1=c2->root;e1;e1=e1->next) {
1478                                                 if (!strcmp(e1->exten, e2->exten)) {
1479                                                         found = 1;
1480                                                         break;
1481                                                 }
1482                                         }
1483                                         if (!found) {
1484                                                 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);
1485                                                 check_contexts_trouble();
1486                                         }
1487
1488                                 }
1489                                 ast_hashtab_end_traversal(t1);
1490                         }
1491                 }
1492                 /* is every priority reflected in the peer_table at the head of the list? */
1493
1494                 /* is every entry in the root list also in the root_table? */
1495                 /* are the per-extension peer_tables in the right place? */
1496
1497                 for(e1 = c2->root; e1; e1 = e1->next) {
1498
1499                         for(e2=e1;e2;e2=e2->peer) {
1500                                 ex.priority = e2->priority;
1501                                 if (e2 != e1 && e2->peer_table) {
1502                                         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 );
1503                                         check_contexts_trouble();
1504                                 }
1505
1506                                 if (e2 != e1 && e2->peer_label_table) {
1507                                         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 );
1508                                         check_contexts_trouble();
1509                                 }
1510
1511                                 if (e2 == e1 && !e2->peer_table){
1512                                         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 );
1513                                         check_contexts_trouble();
1514                                 }
1515
1516                                 if (e2 == e1 && !e2->peer_label_table) {
1517                                         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 );
1518                                         check_contexts_trouble();
1519                                 }
1520
1521
1522                                 e3 = ast_hashtab_lookup(e1->peer_table, &ex);
1523                                 if (!e3) {
1524                                         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 );
1525                                         check_contexts_trouble();
1526                                 }
1527                         }
1528
1529                         if (!e1->peer_table){
1530                                 ast_log(LOG_NOTICE,"Called from: %s:%d: No e1->peer_table!\n", file, line);
1531                                 usleep(500000);
1532                         }
1533
1534                         /* is every entry in the peer_table also in the peer list? */
1535                         t1 = ast_hashtab_start_traversal(e1->peer_table);
1536                         while( (e2 = ast_hashtab_next(t1)) ) {
1537                                 for(e3=e1;e3;e3=e3->peer) {
1538                                         if (e3->priority == e2->priority) {
1539                                                 found = 1;
1540                                                 break;
1541                                         }
1542                                 }
1543                                 if (!found) {
1544                                         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 );
1545                                         check_contexts_trouble();
1546                                 }
1547                         }
1548                         ast_hashtab_end_traversal(t1);
1549                 }
1550         }
1551         return 0;
1552 }
1553 #endif
1554
1555 /*
1556    \note This function is special. It saves the stack so that no matter
1557    how many times it is called, it returns to the same place */
1558 int pbx_exec(struct ast_channel *c,     /*!< Channel */
1559              struct ast_app *app,       /*!< Application */
1560              const char *data)          /*!< Data for execution */
1561 {
1562         int res;
1563         struct ast_module_user *u = NULL;
1564         const char *saved_c_appl;
1565         const char *saved_c_data;
1566
1567         if (ast_channel_cdr(c) && !ast_check_hangup(c))
1568                 ast_cdr_setapp(ast_channel_cdr(c), app->name, data);
1569
1570         /* save channel values */
1571         saved_c_appl= ast_channel_appl(c);
1572         saved_c_data= ast_channel_data(c);
1573
1574         ast_channel_appl_set(c, app->name);
1575         ast_channel_data_set(c, data);
1576         ast_cel_report_event(c, AST_CEL_APP_START, NULL, NULL, NULL);
1577
1578         if (app->module)
1579                 u = __ast_module_user_add(app->module, c);
1580         if (strcasecmp(app->name, "system") && !ast_strlen_zero(data) &&
1581                         strchr(data, '|') && !strchr(data, ',') && !ast_opt_dont_warn) {
1582                 ast_log(LOG_WARNING, "The application delimiter is now the comma, not "
1583                         "the pipe.  Did you forget to convert your dialplan?  (%s(%s))\n",
1584                         app->name, (char *) data);
1585         }
1586         res = app->execute(c, S_OR(data, ""));
1587         if (app->module && u)
1588                 __ast_module_user_remove(app->module, u);
1589         ast_cel_report_event(c, AST_CEL_APP_END, NULL, NULL, NULL);
1590         /* restore channel values */
1591         ast_channel_appl_set(c, saved_c_appl);
1592         ast_channel_data_set(c, saved_c_data);
1593         return res;
1594 }
1595
1596
1597 /*! Go no deeper than this through includes (not counting loops) */
1598 #define AST_PBX_MAX_STACK       128
1599
1600 /*! \brief Find application handle in linked list
1601  */
1602 struct ast_app *pbx_findapp(const char *app)
1603 {
1604         struct ast_app *tmp;
1605
1606         AST_RWLIST_RDLOCK(&apps);
1607         AST_RWLIST_TRAVERSE(&apps, tmp, list) {
1608                 if (!strcasecmp(tmp->name, app))
1609                         break;
1610         }
1611         AST_RWLIST_UNLOCK(&apps);
1612
1613         return tmp;
1614 }
1615
1616 static struct ast_switch *pbx_findswitch(const char *sw)
1617 {
1618         struct ast_switch *asw;
1619
1620         AST_RWLIST_RDLOCK(&switches);
1621         AST_RWLIST_TRAVERSE(&switches, asw, list) {
1622                 if (!strcasecmp(asw->name, sw))
1623                         break;
1624         }
1625         AST_RWLIST_UNLOCK(&switches);
1626
1627         return asw;
1628 }
1629
1630 static inline int include_valid(struct ast_include *i)
1631 {
1632         if (!i->hastime)
1633                 return 1;
1634
1635         return ast_check_timing(&(i->timing));
1636 }
1637
1638 static void pbx_destroy(struct ast_pbx *p)
1639 {
1640         ast_free(p);
1641 }
1642
1643 /* form a tree that fully describes all the patterns in a context's extensions
1644  * in this tree, a "node" represents an individual character or character set
1645  * meant to match the corresponding character in a dial string. The tree
1646  * consists of a series of match_char structs linked in a chain
1647  * via the alt_char pointers. More than one pattern can share the same parts of the
1648  * tree as other extensions with the same pattern to that point.
1649  * My first attempt to duplicate the finding of the 'best' pattern was flawed in that
1650  * I misunderstood the general algorithm. I thought that the 'best' pattern
1651  * was the one with lowest total score. This was not true. Thus, if you have
1652  * patterns "1XXXXX" and "X11111", you would be tempted to say that "X11111" is
1653  * the "best" match because it has fewer X's, and is therefore more specific,
1654  * but this is not how the old algorithm works. It sorts matching patterns
1655  * in a similar collating sequence as sorting alphabetic strings, from left to
1656  * right. Thus, "1XXXXX" comes before "X11111", and would be the "better" match,
1657  * because "1" is more specific than "X".
1658  * So, to accomodate this philosophy, I sort the tree branches along the alt_char
1659  * line so they are lowest to highest in specificity numbers. This way, as soon
1660  * as we encounter our first complete match, we automatically have the "best"
1661  * match and can stop the traversal immediately. Same for CANMATCH/MATCHMORE.
1662  * If anyone would like to resurrect the "wrong" pattern trie searching algorithm,
1663  * they are welcome to revert pbx to before 1 Apr 2008.
1664  * As an example, consider these 4 extensions:
1665  * (a) NXXNXXXXXX
1666  * (b) 307754XXXX
1667  * (c) fax
1668  * (d) NXXXXXXXXX
1669  *
1670  * In the above, between (a) and (d), (a) is a more specific pattern than (d), and would win over
1671  * most numbers. For all numbers beginning with 307754, (b) should always win.
1672  *
1673  * These pattern should form a (sorted) tree that looks like this:
1674  *   { "3" }  --next-->  { "0" }  --next--> { "7" } --next--> { "7" } --next--> { "5" } ... blah ... --> { "X" exten_match: (b) }
1675  *      |
1676  *      |alt
1677  *      |
1678  *   { "f" }  --next-->  { "a" }  --next--> { "x"  exten_match: (c) }
1679  *   { "N" }  --next-->  { "X" }  --next--> { "X" } --next--> { "N" } --next--> { "X" } ... blah ... --> { "X" exten_match: (a) }
1680  *      |                                                        |
1681  *      |                                                        |alt
1682  *      |alt                                                     |
1683  *      |                                                     { "X" } --next--> { "X" } ... blah ... --> { "X" exten_match: (d) }
1684  *      |
1685  *     NULL
1686  *
1687  *   In the above, I could easily turn "N" into "23456789", but I think that a quick "if( *z >= '2' && *z <= '9' )" might take
1688  *   fewer CPU cycles than a call to strchr("23456789",*z), where *z is the char to match...
1689  *
1690  *   traversal is pretty simple: one routine merely traverses the alt list, and for each matching char in the pattern,  it calls itself
1691  *   on the corresponding next pointer, incrementing also the pointer of the string to be matched, and passing the total specificity and length.
1692  *   We pass a pointer to a scoreboard down through, also.
1693  *   The scoreboard isn't as necessary to the revised algorithm, but I kept it as a handy way to return the matched extension.
1694  *   The first complete match ends the traversal, which should make this version of the pattern matcher faster
1695  *   the previous. The same goes for "CANMATCH" or "MATCHMORE"; the first such match ends the traversal. In both
1696  *   these cases, the reason we can stop immediately, is because the first pattern match found will be the "best"
1697  *   according to the sort criteria.
1698  *   Hope the limit on stack depth won't be a problem... this routine should
1699  *   be pretty lean as far a stack usage goes. Any non-match terminates the recursion down a branch.
1700  *
1701  *   In the above example, with the number "3077549999" as the pattern, the traversor could match extensions a, b and d.  All are
1702  *   of length 10; they have total specificities of  24580, 10246, and 25090, respectively, not that this matters
1703  *   at all. (b) wins purely because the first character "3" is much more specific (lower specificity) than "N". I have
1704  *   left the specificity totals in the code as an artifact; at some point, I will strip it out.
1705  *
1706  *   Just how much time this algorithm might save over a plain linear traversal over all possible patterns is unknown,
1707  *   because it's a function of how many extensions are stored in a context. With thousands of extensions, the speedup
1708  *   can be very noticeable. The new matching algorithm can run several hundreds of times faster, if not a thousand or
1709  *   more times faster in extreme cases.
1710  *
1711  *   MatchCID patterns are also supported, and stored in the tree just as the extension pattern is. Thus, you
1712  *   can have patterns in your CID field as well.
1713  *
1714  * */
1715
1716
1717 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)
1718 {
1719         /* if this extension is marked as deleted, then skip this -- if it never shows
1720            on the scoreboard, it will never be found, nor will halt the traversal. */
1721         if (deleted)
1722                 return;
1723         board->total_specificity = spec;
1724         board->total_length = length;
1725         board->exten = exten;
1726         board->last_char = last;
1727         board->node = node;
1728 #ifdef NEED_DEBUG_HERE
1729         ast_log(LOG_NOTICE,"Scoreboarding (LONGER) %s, len=%d, score=%d\n", exten->exten, length, spec);
1730 #endif
1731 }
1732
1733 #ifdef NEED_DEBUG
1734 static void log_match_char_tree(struct match_char *node, char *prefix)
1735 {
1736         char extenstr[40];
1737         struct ast_str *my_prefix = ast_str_alloca(1024);
1738
1739         extenstr[0] = '\0';
1740
1741         if (node && node->exten)
1742                 snprintf(extenstr, sizeof(extenstr), "(%p)", node->exten);
1743
1744         if (strlen(node->x) > 1) {
1745                 ast_debug(1, "%s[%s]:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y':'N',
1746                         node->deleted? 'D':'-', node->specificity, node->exten? "EXTEN:":"",
1747                         node->exten ? node->exten->exten : "", extenstr);
1748         } else {
1749                 ast_debug(1, "%s%s:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y':'N',
1750                         node->deleted? 'D':'-', node->specificity, node->exten? "EXTEN:":"",
1751                         node->exten ? node->exten->exten : "", extenstr);
1752         }
1753
1754         ast_str_set(&my_prefix, 0, "%s+       ", prefix);
1755
1756         if (node->next_char)
1757                 log_match_char_tree(node->next_char, ast_str_buffer(my_prefix));
1758
1759         if (node->alt_char)
1760                 log_match_char_tree(node->alt_char, prefix);
1761 }
1762 #endif
1763
1764 static void cli_match_char_tree(struct match_char *node, char *prefix, int fd)
1765 {
1766         char extenstr[40];
1767         struct ast_str *my_prefix = ast_str_alloca(1024);
1768
1769         extenstr[0] = '\0';
1770
1771         if (node->exten) {
1772                 snprintf(extenstr, sizeof(extenstr), "(%p)", node->exten);
1773         }
1774
1775         if (strlen(node->x) > 1) {
1776                 ast_cli(fd, "%s[%s]:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y' : 'N',
1777                         node->deleted ? 'D' : '-', node->specificity, node->exten? "EXTEN:" : "",
1778                         node->exten ? node->exten->exten : "", extenstr);
1779         } else {
1780                 ast_cli(fd, "%s%s:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y' : 'N',
1781                         node->deleted ? 'D' : '-', node->specificity, node->exten? "EXTEN:" : "",
1782                         node->exten ? node->exten->exten : "", extenstr);
1783         }
1784
1785         ast_str_set(&my_prefix, 0, "%s+       ", prefix);
1786
1787         if (node->next_char)
1788                 cli_match_char_tree(node->next_char, ast_str_buffer(my_prefix), fd);
1789
1790         if (node->alt_char)
1791                 cli_match_char_tree(node->alt_char, prefix, fd);
1792 }
1793
1794 static struct ast_exten *get_canmatch_exten(struct match_char *node)
1795 {
1796         /* find the exten at the end of the rope */
1797         struct match_char *node2 = node;
1798
1799         for (node2 = node; node2; node2 = node2->next_char) {
1800                 if (node2->exten) {
1801 #ifdef NEED_DEBUG_HERE
1802                         ast_log(LOG_NOTICE,"CanMatch_exten returns exten %s(%p)\n", node2->exten->exten, node2->exten);
1803 #endif
1804                         return node2->exten;
1805                 }
1806         }
1807 #ifdef NEED_DEBUG_HERE
1808         ast_log(LOG_NOTICE,"CanMatch_exten returns NULL, match_char=%s\n", node->x);
1809 #endif
1810         return 0;
1811 }
1812
1813 static struct ast_exten *trie_find_next_match(struct match_char *node)
1814 {
1815         struct match_char *m3;
1816         struct match_char *m4;
1817         struct ast_exten *e3;
1818
1819         if (node && node->x[0] == '.' && !node->x[1]) { /* dot and ! will ALWAYS be next match in a matchmore */
1820                 return node->exten;
1821         }
1822
1823         if (node && node->x[0] == '!' && !node->x[1]) {
1824                 return node->exten;
1825         }
1826
1827         if (!node || !node->next_char) {
1828                 return NULL;
1829         }
1830
1831         m3 = node->next_char;
1832
1833         if (m3->exten) {
1834                 return m3->exten;
1835         }
1836         for (m4 = m3->alt_char; m4; m4 = m4->alt_char) {
1837                 if (m4->exten) {
1838                         return m4->exten;
1839                 }
1840         }
1841         for (m4 = m3; m4; m4 = m4->alt_char) {
1842                 e3 = trie_find_next_match(m3);
1843                 if (e3) {
1844                         return e3;
1845                 }
1846         }
1847
1848         return NULL;
1849 }
1850
1851 #ifdef DEBUG_THIS
1852 static char *action2str(enum ext_match_t action)
1853 {
1854         switch (action) {
1855         case E_MATCH:
1856                 return "MATCH";
1857         case E_CANMATCH:
1858                 return "CANMATCH";
1859         case E_MATCHMORE:
1860                 return "MATCHMORE";
1861         case E_FINDLABEL:
1862                 return "FINDLABEL";
1863         case E_SPAWN:
1864                 return "SPAWN";
1865         default:
1866                 return "?ACTION?";
1867         }
1868 }
1869
1870 #endif
1871
1872 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)
1873 {
1874         struct match_char *p; /* note minimal stack storage requirements */
1875         struct ast_exten pattern = { .label = label };
1876 #ifdef DEBUG_THIS
1877         if (tree)
1878                 ast_log(LOG_NOTICE,"new_find_extension called with %s on (sub)tree %s action=%s\n", str, tree->x, action2str(action));
1879         else
1880                 ast_log(LOG_NOTICE,"new_find_extension called with %s on (sub)tree NULL action=%s\n", str, action2str(action));
1881 #endif
1882         for (p = tree; p; p = p->alt_char) {
1883                 if (p->is_pattern) {
1884                         if (p->x[0] == 'N') {
1885                                 if (p->x[1] == 0 && *str >= '2' && *str <= '9' ) {
1886 #define NEW_MATCHER_CHK_MATCH          \
1887                                         if (p->exten && !(*(str + 1))) { /* if a shorter pattern matches along the way, might as well report it */             \
1888                                                 if (action == E_MATCH || action == E_SPAWN || action == E_FINDLABEL) { /* if in CANMATCH/MATCHMORE, don't let matches get in the way */   \
1889                                                         update_scoreboard(score, length + 1, spec + p->specificity, p->exten, 0, callerid, p->deleted, p);                 \
1890                                                         if (!p->deleted) {                                                                                           \
1891                                                                 if (action == E_FINDLABEL) {                                                                             \
1892                                                                         if (ast_hashtab_lookup(score->exten->peer_label_table, &pattern)) {                                  \
1893                                                                                 ast_debug(4, "Found label in preferred extension\n");                                            \
1894                                                                                 return;                                                                                          \
1895                                                                         }                                                                                                    \
1896                                                                 } else {                                                                                                 \
1897                                                                         ast_debug(4, "returning an exact match-- first found-- %s\n", p->exten->exten);                       \
1898                                                                         return; /* the first match, by definition, will be the best, because of the sorted tree */           \
1899                                                                 }                                                                                                        \
1900                                                         }                                                                                                            \
1901                                                 }                                                                                                                \
1902                                         }
1903
1904 #define NEW_MATCHER_RECURSE                \
1905                                         if (p->next_char && (*(str + 1) || (p->next_char->x[0] == '/' && p->next_char->x[1] == 0)                 \
1906                                                        || p->next_char->x[0] == '!')) {                                          \
1907                                                 if (*(str + 1) || p->next_char->x[0] == '!') {                                                         \
1908                                                         new_find_extension(str + 1, score, p->next_char, length + 1, spec + p->specificity, callerid, label, action); \
1909                                                         if (score->exten)  {                                                                             \
1910                                                         ast_debug(4 ,"returning an exact match-- %s\n", score->exten->exten);                         \
1911                                                                 return; /* the first match is all we need */                                                 \
1912                                                         }                                                                                                                                                \
1913                                                 } else {                                                                                             \
1914                                                         new_find_extension("/", score, p->next_char, length + 1, spec + p->specificity, callerid, label, action);        \
1915                                                         if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {      \
1916                                                         ast_debug(4,"returning a (can/more) match--- %s\n", score->exten ? score->exten->exten :     \
1917                                                "NULL");                                                                        \
1918                                                                 return; /* the first match is all we need */                                                 \
1919                                                         }                                                                                                                                                \
1920                                                 }                                                                                                    \
1921                                         } else if ((p->next_char || action == E_CANMATCH) && !*(str + 1)) {                                                                  \
1922                                                 score->canmatch = 1;                                                                                 \
1923                                                 score->canmatch_exten = get_canmatch_exten(p);                                                       \
1924                                                 if (action == E_CANMATCH || action == E_MATCHMORE) {                                                 \
1925                                                 ast_debug(4, "returning a canmatch/matchmore--- str=%s\n", str);                                  \
1926                                                         return;                                                                                          \
1927                                                 }                                                                                                                                                    \
1928                                         }
1929
1930                                         NEW_MATCHER_CHK_MATCH;
1931                                         NEW_MATCHER_RECURSE;
1932                                 }
1933                         } else if (p->x[0] == 'Z') {
1934                                 if (p->x[1] == 0 && *str >= '1' && *str <= '9' ) {
1935                                         NEW_MATCHER_CHK_MATCH;
1936                                         NEW_MATCHER_RECURSE;
1937                                 }
1938                         } else if (p->x[0] == 'X') {
1939                                 if (p->x[1] == 0 && *str >= '0' && *str <= '9' ) {
1940                                         NEW_MATCHER_CHK_MATCH;
1941                                         NEW_MATCHER_RECURSE;
1942                                 }
1943                         } else if (p->x[0] == '.' && p->x[1] == 0) {
1944                                 /* how many chars will the . match against? */
1945                                 int i = 0;
1946                                 const char *str2 = str;
1947                                 while (*str2 && *str2 != '/') {
1948                                         str2++;
1949                                         i++;
1950                                 }
1951                                 if (p->exten && *str2 != '/') {
1952                                         update_scoreboard(score, length + i, spec + (i * p->specificity), p->exten, '.', callerid, p->deleted, p);
1953                                         if (score->exten) {
1954                                                 ast_debug(4,"return because scoreboard has a match with '/'--- %s\n", score->exten->exten);
1955                                                 return; /* the first match is all we need */
1956                                         }
1957                                 }
1958                                 if (p->next_char && p->next_char->x[0] == '/' && p->next_char->x[1] == 0) {
1959                                         new_find_extension("/", score, p->next_char, length + i, spec+(p->specificity*i), callerid, label, action);
1960                                         if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
1961                                                 ast_debug(4, "return because scoreboard has exact match OR CANMATCH/MATCHMORE & canmatch set--- %s\n", score->exten ? score->exten->exten : "NULL");
1962                                                 return; /* the first match is all we need */
1963                                         }
1964                                 }
1965                         } else if (p->x[0] == '!' && p->x[1] == 0) {
1966                                 /* how many chars will the . match against? */
1967                                 int i = 1;
1968                                 const char *str2 = str;
1969                                 while (*str2 && *str2 != '/') {
1970                                         str2++;
1971                                         i++;
1972                                 }
1973                                 if (p->exten && *str2 != '/') {
1974                                         update_scoreboard(score, length + 1, spec + (p->specificity * i), p->exten, '!', callerid, p->deleted, p);
1975                                         if (score->exten) {
1976                                                 ast_debug(4, "return because scoreboard has a '!' match--- %s\n", score->exten->exten);
1977                                                 return; /* the first match is all we need */
1978                                         }
1979                                 }
1980                                 if (p->next_char && p->next_char->x[0] == '/' && p->next_char->x[1] == 0) {
1981                                         new_find_extension("/", score, p->next_char, length + i, spec + (p->specificity * i), callerid, label, action);
1982                                         if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
1983                                                 ast_debug(4, "return because scoreboard has exact match OR CANMATCH/MATCHMORE & canmatch set with '/' and '!'--- %s\n", score->exten ? score->exten->exten : "NULL");
1984                                                 return; /* the first match is all we need */
1985                                         }
1986                                 }
1987                         } else if (p->x[0] == '/' && p->x[1] == 0) {
1988                                 /* the pattern in the tree includes the cid match! */
1989                                 if (p->next_char && callerid && *callerid) {
1990                                         new_find_extension(callerid, score, p->next_char, length + 1, spec, callerid, label, action);
1991                                         if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
1992                                                 ast_debug(4, "return because scoreboard has exact match OR CANMATCH/MATCHMORE & canmatch set with '/'--- %s\n", score->exten ? score->exten->exten : "NULL");
1993                                                 return; /* the first match is all we need */
1994                                         }
1995                                 }
1996                         } else if (strchr(p->x, *str)) {
1997                                 ast_debug(4, "Nothing strange about this match\n");
1998                                 NEW_MATCHER_CHK_MATCH;
1999                                 NEW_MATCHER_RECURSE;
2000                         }
2001                 } else if (strchr(p->x, *str)) {
2002                         ast_debug(4, "Nothing strange about this match\n");
2003                         NEW_MATCHER_CHK_MATCH;
2004                         NEW_MATCHER_RECURSE;
2005                 }
2006         }
2007         ast_debug(4, "return at end of func\n");
2008 }
2009
2010 /* the algorithm for forming the extension pattern tree is also a bit simple; you
2011  * traverse all the extensions in a context, and for each char of the extension,
2012  * you see if it exists in the tree; if it doesn't, you add it at the appropriate
2013  * spot. What more can I say? At the end of each exten, you cap it off by adding the
2014  * address of the extension involved. Duplicate patterns will be complained about.
2015  *
2016  * Ideally, this would be done for each context after it is created and fully
2017  * filled. It could be done as a finishing step after extensions.conf or .ael is
2018  * loaded, or it could be done when the first search is encountered. It should only
2019  * have to be done once, until the next unload or reload.
2020  *
2021  * I guess forming this pattern tree would be analogous to compiling a regex. Except
2022  * that a regex only handles 1 pattern, really. This trie holds any number
2023  * of patterns. Well, really, it **could** be considered a single pattern,
2024  * where the "|" (or) operator is allowed, I guess, in a way, sort of...
2025  */
2026
2027 static struct match_char *already_in_tree(struct match_char *current, char *pat, int is_pattern)
2028 {
2029         struct match_char *t;
2030
2031         if (!current) {
2032                 return 0;
2033         }
2034
2035         for (t = current; t; t = t->alt_char) {
2036                 if (is_pattern == t->is_pattern && !strcmp(pat, t->x)) {/* uh, we may want to sort exploded [] contents to make matching easy */
2037                         return t;
2038                 }
2039         }
2040
2041         return 0;
2042 }
2043
2044 /* The first arg is the location of the tree ptr, or the
2045    address of the next_char ptr in the node, so we can mess
2046    with it, if we need to insert at the beginning of the list */
2047
2048 static void insert_in_next_chars_alt_char_list(struct match_char **parent_ptr, struct match_char *node)
2049 {
2050         struct match_char *curr, *lcurr;
2051
2052         /* insert node into the tree at "current", so the alt_char list from current is
2053            sorted in increasing value as you go to the leaves */
2054         if (!(*parent_ptr)) {
2055                 *parent_ptr = node;
2056                 return;
2057         }
2058
2059         if ((*parent_ptr)->specificity > node->specificity) {
2060                 /* insert at head */
2061                 node->alt_char = (*parent_ptr);
2062                 *parent_ptr = node;
2063                 return;
2064         }
2065
2066         lcurr = *parent_ptr;
2067         for (curr = (*parent_ptr)->alt_char; curr; curr = curr->alt_char) {
2068                 if (curr->specificity > node->specificity) {
2069                         node->alt_char = curr;
2070                         lcurr->alt_char = node;
2071                         break;
2072                 }
2073                 lcurr = curr;
2074         }
2075
2076         if (!curr) {
2077                 lcurr->alt_char = node;
2078         }
2079
2080 }
2081
2082 struct pattern_node {
2083         /*! Pattern node specificity */
2084         int specif;
2085         /*! Pattern node match characters. */
2086         char buf[256];
2087 };
2088
2089 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)
2090 {
2091         struct match_char *m;
2092
2093         if (!(m = ast_calloc(1, sizeof(*m) + strlen(pattern->buf)))) {
2094                 return NULL;
2095         }
2096
2097         /* strcpy is safe here since we know its size and have allocated
2098          * just enough space for when we allocated m
2099          */
2100         strcpy(m->x, pattern->buf);
2101
2102         /* the specificity scores are the same as used in the old
2103            pattern matcher. */
2104         m->is_pattern = is_pattern;
2105         if (pattern->specif == 1 && is_pattern && pattern->buf[0] == 'N') {
2106                 m->specificity = 0x0832;
2107         } else if (pattern->specif == 1 && is_pattern && pattern->buf[0] == 'Z') {
2108                 m->specificity = 0x0931;
2109         } else if (pattern->specif == 1 && is_pattern && pattern->buf[0] == 'X') {
2110                 m->specificity = 0x0a30;
2111         } else if (pattern->specif == 1 && is_pattern && pattern->buf[0] == '.') {
2112                 m->specificity = 0x18000;
2113         } else if (pattern->specif == 1 && is_pattern && pattern->buf[0] == '!') {
2114                 m->specificity = 0x28000;
2115         } else {
2116                 m->specificity = pattern->specif;
2117         }
2118
2119         if (!con->pattern_tree) {
2120                 insert_in_next_chars_alt_char_list(&con->pattern_tree, m);
2121         } else {
2122                 if (already) { /* switch to the new regime (traversing vs appending)*/
2123                         insert_in_next_chars_alt_char_list(nextcharptr, m);
2124                 } else {
2125                         insert_in_next_chars_alt_char_list(&current->next_char, m);
2126                 }
2127         }
2128
2129         return m;
2130 }
2131
2132 /*!
2133  * \internal
2134  * \brief Extract the next exten pattern node.
2135  *
2136  * \param node Pattern node to fill.
2137  * \param src Next source character to read.
2138  * \param pattern TRUE if the exten is a pattern.
2139  * \param extenbuf Original exten buffer to use in diagnostic messages.
2140  *
2141  * \retval Ptr to next extenbuf pos to read.
2142  */
2143 static const char *get_pattern_node(struct pattern_node *node, const char *src, int pattern, const char *extenbuf)
2144 {
2145 #define INC_DST_OVERFLOW_CHECK                                                  \
2146         do {                                                                                            \
2147                 if (dst - node->buf < sizeof(node->buf) - 1) {  \
2148                         ++dst;                                                                          \
2149                 } else {                                                                                \
2150                         overflow = 1;                                                           \
2151                 }                                                                                               \
2152         } while (0)
2153
2154         node->specif = 0;
2155         node->buf[0] = '\0';
2156         while (*src) {
2157                 if (*src == '[' && pattern) {
2158                         char *dst = node->buf;
2159                         const char *src_next;
2160                         int length;
2161                         int overflow = 0;
2162
2163                         /* get past the '[' */
2164                         ++src;
2165                         for (;;) {
2166                                 if (*src == '\\') {
2167                                         /* Escaped character. */
2168                                         ++src;
2169                                         if (*src == '[' || *src == '\\' || *src == '-' || *src == ']') {
2170                                                 *dst = *src++;
2171                                                 INC_DST_OVERFLOW_CHECK;
2172                                         }
2173                                 } else if (*src == '-') {
2174                                         unsigned char first;
2175                                         unsigned char last;
2176
2177                                         src_next = src;
2178                                         first = *(src_next - 1);
2179                                         last = *++src_next;
2180
2181                                         if (last == '\\') {
2182                                                 /* Escaped character. */
2183                                                 last = *++src_next;
2184                                         }
2185
2186                                         /* Possible char range. */
2187                                         if (node->buf[0] && last) {
2188                                                 /* Expand the char range. */
2189                                                 while (++first <= last) {
2190                                                         *dst = first;
2191                                                         INC_DST_OVERFLOW_CHECK;
2192                                                 }
2193                                                 src = src_next + 1;
2194                                         } else {
2195                                                 /*
2196                                                  * There was no left or right char for the range.
2197                                                  * It is just a '-'.
2198                                                  */
2199                                                 *dst = *src++;
2200                                                 INC_DST_OVERFLOW_CHECK;
2201                                         }
2202                                 } else if (*src == '\0') {
2203                                         ast_log(LOG_WARNING,
2204                                                 "A matching ']' was not found for '[' in exten pattern '%s'\n",
2205                                                 extenbuf);
2206                                         break;
2207                                 } else if (*src == ']') {
2208                                         ++src;
2209                                         break;
2210                                 } else {
2211                                         *dst = *src++;
2212                                         INC_DST_OVERFLOW_CHECK;
2213                                 }
2214                         }
2215                         /* null terminate the exploded range */
2216                         *dst = '\0';
2217
2218                         if (overflow) {
2219                                 ast_log(LOG_ERROR,
2220                                         "Expanded character set too large to deal with in exten pattern '%s'. Ignoring character set.\n",
2221                                         extenbuf);
2222                                 node->buf[0] = '\0';
2223                                 continue;
2224                         }
2225
2226                         /* Sort the characters in character set. */
2227                         length = strlen(node->buf);
2228                         if (!length) {
2229                                 ast_log(LOG_WARNING, "Empty character set in exten pattern '%s'. Ignoring.\n",
2230                                         extenbuf);
2231                                 node->buf[0] = '\0';
2232                                 continue;
2233                         }
2234                         qsort(node->buf, length, 1, compare_char);
2235
2236                         /* Remove duplicate characters from character set. */
2237                         dst = node->buf;
2238                         src_next = node->buf;
2239                         while (*src_next++) {
2240                                 if (*dst != *src_next) {
2241                                         *++dst = *src_next;
2242                                 }
2243                         }
2244
2245                         length = strlen(node->buf);
2246                         length <<= 8;
2247                         node->specif = length | (unsigned char) node->buf[0];
2248                         break;
2249                 } else if (*src == '-') {
2250                         /* Skip dashes in all extensions. */
2251                         ++src;
2252                 } else {
2253                         if (*src == '\\') {
2254                                 /*
2255                                  * XXX The escape character here does not remove any special
2256                                  * meaning to characters except the '[', '\\', and '-'
2257                                  * characters since they are special only in this function.
2258                                  */
2259                                 node->buf[0] = *++src;
2260                                 if (!node->buf[0]) {
2261                                         break;
2262                                 }
2263                         } else {
2264                                 node->buf[0] = *src;
2265                                 if (pattern) {
2266                                         /* make sure n,x,z patterns are canonicalized to N,X,Z */
2267                                         if (node->buf[0] == 'n') {
2268                                                 node->buf[0] = 'N';
2269                                         } else if (node->buf[0] == 'x') {
2270                                                 node->buf[0] = 'X';
2271                                         } else if (node->buf[0] == 'z') {
2272                                                 node->buf[0] = 'Z';
2273                                         }
2274                                 }
2275                         }
2276                         node->buf[1] = '\0';
2277                         node->specif = 1;
2278                         ++src;
2279                         break;
2280                 }
2281         }
2282         return src;
2283
2284 #undef INC_DST_OVERFLOW_CHECK
2285 }
2286
2287 static struct match_char *add_exten_to_pattern_tree(struct ast_context *con, struct ast_exten *e1, int findonly)
2288 {
2289         struct match_char *m1 = NULL;
2290         struct match_char *m2 = NULL;
2291         struct match_char **m0;
2292         const char *pos;
2293         int already;
2294         int pattern = 0;
2295         int idx_cur;
2296         int idx_next;
2297         char extenbuf[512];
2298         struct pattern_node pat_node[2];
2299
2300         if (e1->matchcid) {
2301                 if (sizeof(extenbuf) < strlen(e1->exten) + strlen(e1->cidmatch) + 2) {
2302                         ast_log(LOG_ERROR,
2303                                 "The pattern %s/%s is too big to deal with: it will be ignored! Disaster!\n",
2304                                 e1->exten, e1->cidmatch);
2305                         return NULL;
2306                 }
2307                 sprintf(extenbuf, "%s/%s", e1->exten, e1->cidmatch);/* Safe.  We just checked. */
2308         } else {
2309                 ast_copy_string(extenbuf, e1->exten, sizeof(extenbuf));
2310         }
2311
2312 #ifdef NEED_DEBUG
2313         ast_debug(1, "Adding exten %s to tree\n", extenbuf);
2314 #endif
2315         m1 = con->pattern_tree; /* each pattern starts over at the root of the pattern tree */
2316         m0 = &con->pattern_tree;
2317         already = 1;
2318
2319         pos = extenbuf;
2320         if (*pos == '_') {
2321                 pattern = 1;
2322                 ++pos;
2323         }
2324         idx_cur = 0;
2325         pos = get_pattern_node(&pat_node[idx_cur], pos, pattern, extenbuf);
2326         for (; pat_node[idx_cur].buf[0]; idx_cur = idx_next) {
2327                 idx_next = (idx_cur + 1) % ARRAY_LEN(pat_node);
2328                 pos = get_pattern_node(&pat_node[idx_next], pos, pattern, extenbuf);
2329
2330                 /* See about adding node to tree. */
2331                 m2 = NULL;
2332                 if (already && (m2 = already_in_tree(m1, pat_node[idx_cur].buf, pattern))
2333                         && m2->next_char) {
2334                         if (!pat_node[idx_next].buf[0]) {
2335                                 /*
2336                                  * This is the end of the pattern, but not the end of the tree.
2337                                  * Mark this node with the exten... a shorter pattern might win
2338                                  * if the longer one doesn't match.
2339                                  */
2340                                 if (findonly) {
2341                                         return m2;
2342                                 }
2343                                 if (m2->exten) {
2344                                         ast_log(LOG_WARNING, "Found duplicate exten. Had %s found %s\n",
2345                                                 m2->deleted ? "(deleted/invalid)" : m2->exten->exten, e1->exten);
2346                                 }
2347                                 m2->exten = e1;
2348                                 m2->deleted = 0;
2349                         }
2350                         m1 = m2->next_char; /* m1 points to the node to compare against */
2351                         m0 = &m2->next_char; /* m0 points to the ptr that points to m1 */
2352                 } else { /* not already OR not m2 OR nor m2->next_char */
2353                         if (m2) {
2354                                 if (findonly) {
2355                                         return m2;
2356                                 }
2357                                 m1 = m2; /* while m0 stays the same */
2358                         } else {
2359                                 if (findonly) {
2360                                         return m1;
2361                                 }
2362                                 m1 = add_pattern_node(con, m1, &pat_node[idx_cur], pattern, already, m0);
2363                                 if (!m1) { /* m1 is the node just added */
2364                                         return NULL;
2365                                 }
2366                                 m0 = &m1->next_char;
2367                         }
2368                         if (!pat_node[idx_next].buf[0]) {
2369                                 if (m2 && m2->exten) {
2370                                         ast_log(LOG_WARNING, "Found duplicate exten. Had %s found %s\n",
2371                                                 m2->deleted ? "(deleted/invalid)" : m2->exten->exten, e1->exten);
2372                                 }
2373                                 m1->deleted = 0;
2374                                 m1->exten = e1;
2375                         }
2376
2377                         /* The 'already' variable is a mini-optimization designed to make it so that we
2378                          * don't have to call already_in_tree when we know it will return false.
2379                          */
2380                         already = 0;
2381                 }
2382         }
2383         return m1;
2384 }
2385
2386 static void create_match_char_tree(struct ast_context *con)
2387 {
2388         struct ast_hashtab_iter *t1;
2389         struct ast_exten *e1;
2390 #ifdef NEED_DEBUG
2391         int biggest_bucket, resizes, numobjs, numbucks;
2392
2393         ast_debug(1, "Creating Extension Trie for context %s(%p)\n", con->name, con);
2394         ast_hashtab_get_stats(con->root_table, &biggest_bucket, &resizes, &numobjs, &numbucks);
2395         ast_debug(1, "This tree has %d objects in %d bucket lists, longest list=%d objects, and has resized %d times\n",
2396                         numobjs, numbucks, biggest_bucket, resizes);
2397 #endif
2398         t1 = ast_hashtab_start_traversal(con->root_table);
2399         while ((e1 = ast_hashtab_next(t1))) {
2400                 if (e1->exten) {
2401                         add_exten_to_pattern_tree(con, e1, 0);
2402                 } else {
2403                         ast_log(LOG_ERROR, "Attempt to create extension with no extension name.\n");
2404                 }
2405         }
2406         ast_hashtab_end_traversal(t1);
2407 }
2408
2409 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! */
2410 {
2411         /* destroy all the alternates */
2412         if (pattern_tree->alt_char) {
2413                 destroy_pattern_tree(pattern_tree->alt_char);
2414                 pattern_tree->alt_char = 0;
2415         }
2416         /* destroy all the nexts */
2417         if (pattern_tree->next_char) {
2418                 destroy_pattern_tree(pattern_tree->next_char);
2419                 pattern_tree->next_char = 0;
2420         }
2421         pattern_tree->exten = 0; /* never hurts to make sure there's no pointers laying around */
2422         ast_free(pattern_tree);
2423 }
2424
2425 /*
2426  * Special characters used in patterns:
2427  *      '_'     underscore is the leading character of a pattern.
2428  *              In other position it is treated as a regular char.
2429  *      .       one or more of any character. Only allowed at the end of
2430  *              a pattern.
2431  *      !       zero or more of anything. Also impacts the result of CANMATCH
2432  *              and MATCHMORE. Only allowed at the end of a pattern.
2433  *              In the core routine, ! causes a match with a return code of 2.
2434  *              In turn, depending on the search mode: (XXX check if it is implemented)
2435  *              - E_MATCH retuns 1 (does match)
2436  *              - E_MATCHMORE returns 0 (no match)
2437  *              - E_CANMATCH returns 1 (does match)
2438  *
2439  *      /       should not appear as it is considered the separator of the CID info.
2440  *              XXX at the moment we may stop on this char.
2441  *
2442  *      X Z N   match ranges 0-9, 1-9, 2-9 respectively.
2443  *      [       denotes the start of a set of character. Everything inside
2444  *              is considered literally. We can have ranges a-d and individual
2445  *              characters. A '[' and '-' can be considered literally if they
2446  *              are just before ']'.
2447  *              XXX currently there is no way to specify ']' in a range, nor \ is
2448  *              considered specially.
2449  *
2450  * When we compare a pattern with a specific extension, all characters in the extension
2451  * itself are considered literally.
2452  * XXX do we want to consider space as a separator as well ?
2453  * XXX do we want to consider the separators in non-patterns as well ?
2454  */
2455
2456 /*!
2457  * \brief helper functions to sort extensions and patterns in the desired way,
2458  * so that more specific patterns appear first.
2459  *
2460  * ext_cmp1 compares individual characters (or sets of), returning
2461  * an int where bits 0-7 are the ASCII code of the first char in the set,
2462  * while bit 8-15 are the cardinality of the set minus 1.
2463  * This way more specific patterns (smaller cardinality) appear first.
2464  * Wildcards have a special value, so that we can directly compare them to
2465  * sets by subtracting the two values. In particular:
2466  *  0x000xx             one character, xx
2467  *  0x0yyxx             yy character set starting with xx
2468  *  0x10000             '.' (one or more of anything)
2469  *  0x20000             '!' (zero or more of anything)
2470  *  0x30000             NUL (end of string)
2471  *  0x40000             error in set.
2472  * The pointer to the string is advanced according to needs.
2473  * NOTES:
2474  *      1. the empty set is equivalent to NUL.
2475  *      2. given that a full set has always 0 as the first element,
2476  *         we could encode the special cases as 0xffXX where XX
2477  *         is 1, 2, 3, 4 as used above.
2478  */
2479 static int ext_cmp1(const char **p, unsigned char *bitwise)
2480 {
2481         int c, cmin = 0xff, count = 0;
2482         const char *end;
2483
2484         /* load value and advance pointer */
2485         c = *(*p)++;
2486
2487         /* always return unless we have a set of chars */
2488         switch (toupper(c)) {
2489         default:        /* ordinary character */
2490                 bitwise[c / 8] = 1 << (c % 8);
2491                 return 0x0100 | (c & 0xff);
2492
2493         case 'N':       /* 2..9 */
2494                 bitwise[6] = 0xfc;
2495                 bitwise[7] = 0x03;
2496                 return 0x0800 | '2';
2497
2498         case 'X':       /* 0..9 */
2499                 bitwise[6] = 0xff;
2500                 bitwise[7] = 0x03;
2501                 return 0x0A00 | '0';
2502
2503         case 'Z':       /* 1..9 */
2504                 bitwise[6] = 0xfe;
2505                 bitwise[7] = 0x03;
2506                 return 0x0900 | '1';
2507
2508         case '.':       /* wildcard */
2509                 return 0x18000;
2510
2511         case '!':       /* earlymatch */
2512                 return 0x28000; /* less specific than NULL */
2513
2514         case '\0':      /* empty string */
2515                 *p = NULL;
2516                 return 0x30000;
2517
2518         case '[':       /* pattern */
2519                 break;
2520         }
2521         /* locate end of set */
2522         end = strchr(*p, ']');
2523
2524         if (end == NULL) {
2525                 ast_log(LOG_WARNING, "Wrong usage of [] in the extension\n");
2526                 return 0x40000; /* XXX make this entry go last... */
2527         }
2528
2529         for (; *p < end  ; (*p)++) {
2530                 unsigned char c1, c2;   /* first-last char in range */
2531                 c1 = (unsigned char)((*p)[0]);
2532                 if (*p + 2 < end && (*p)[1] == '-') { /* this is a range */
2533                         c2 = (unsigned char)((*p)[2]);
2534                         *p += 2;    /* skip a total of 3 chars */
2535                 } else {        /* individual character */
2536                         c2 = c1;
2537                 }
2538                 if (c1 < cmin) {
2539                         cmin = c1;
2540                 }
2541                 for (; c1 <= c2; c1++) {
2542                         unsigned char mask = 1 << (c1 % 8);
2543                         /*!\note If two patterns score the same, the one with the lowest
2544                          * ascii values will compare as coming first. */
2545                         /* Flag the character as included (used) and count it. */
2546                         if (!(bitwise[ c1 / 8 ] & mask)) {
2547                                 bitwise[ c1 / 8 ] |= mask;
2548                                 count += 0x100;
2549                         }
2550                 }
2551         }
2552         (*p)++;
2553         return count == 0 ? 0x30000 : (count | cmin);
2554 }
2555
2556 /*!
2557  * \brief the full routine to compare extensions in rules.
2558  */
2559 static int ext_cmp(const char *a, const char *b)
2560 {
2561         /* make sure non-patterns come first.
2562          * If a is not a pattern, it either comes first or
2563          * we do a more complex pattern comparison.
2564          */
2565         int ret = 0;
2566
2567         if (a[0] != '_')
2568                 return (b[0] == '_') ? -1 : strcmp(a, b);
2569
2570         /* Now we know a is a pattern; if b is not, a comes first */
2571         if (b[0] != '_')
2572                 return 1;
2573
2574         /* ok we need full pattern sorting routine.
2575          * skip past the underscores */
2576         ++a; ++b;
2577         do {
2578                 unsigned char bitwise[2][32] = { { 0, } };
2579                 ret = ext_cmp1(&a, bitwise[0]) - ext_cmp1(&b, bitwise[1]);
2580                 if (ret == 0) {
2581                         /* Are the classes different, even though they score the same? */
2582                         ret = memcmp(bitwise[0], bitwise[1], 32);
2583                 }
2584         } while (!ret && a && b);
2585         if (ret == 0) {
2586                 return 0;
2587         } else {
2588                 return (ret > 0) ? 1 : -1;
2589         }
2590 }
2591
2592 int ast_extension_cmp(const char *a, const char *b)
2593 {
2594         return ext_cmp(a, b);
2595 }
2596
2597 /*!
2598  * \internal
2599  * \brief used ast_extension_{match|close}
2600  * mode is as follows:
2601  *      E_MATCH         success only on exact match
2602  *      E_MATCHMORE     success only on partial match (i.e. leftover digits in pattern)
2603  *      E_CANMATCH      either of the above.
2604  * \retval 0 on no-match
2605  * \retval 1 on match
2606  * \retval 2 on early match.
2607  */
2608
2609 static int _extension_match_core(const char *pattern, const char *data, enum ext_match_t mode)
2610 {
2611         mode &= E_MATCH_MASK;   /* only consider the relevant bits */
2612
2613 #ifdef NEED_DEBUG_HERE
2614         ast_log(LOG_NOTICE,"match core: pat: '%s', dat: '%s', mode=%d\n", pattern, data, (int)mode);
2615 #endif
2616
2617         if ( (mode == E_MATCH) && (pattern[0] == '_') && (!strcasecmp(pattern,data)) ) { /* note: if this test is left out, then _x. will not match _x. !!! */
2618 #ifdef NEED_DEBUG_HERE
2619                 ast_log(LOG_NOTICE,"return (1) - pattern matches pattern\n");
2620 #endif
2621                 return 1;
2622         }
2623
2624         if (pattern[0] != '_') { /* not a pattern, try exact or partial match */
2625                 int ld = strlen(data), lp = strlen(pattern);
2626
2627                 if (lp < ld) {          /* pattern too short, cannot match */
2628 #ifdef NEED_DEBUG_HERE
2629                         ast_log(LOG_NOTICE,"return (0) - pattern too short, cannot match\n");
2630 #endif
2631                         return 0;
2632                 }
2633                 /* depending on the mode, accept full or partial match or both */
2634                 if (mode == E_MATCH) {
2635 #ifdef NEED_DEBUG_HERE
2636                         ast_log(LOG_NOTICE,"return (!strcmp(%s,%s) when mode== E_MATCH)\n", pattern, data);
2637 #endif
2638                         return !strcmp(pattern, data); /* 1 on match, 0 on fail */
2639                 }
2640                 if (ld == 0 || !strncasecmp(pattern, data, ld)) { /* partial or full match */
2641 #ifdef NEED_DEBUG_HERE
2642                         ast_log(LOG_NOTICE,"return (mode(%d) == E_MATCHMORE ? lp(%d) > ld(%d) : 1)\n", mode, lp, ld);
2643 #endif
2644                         return (mode == E_MATCHMORE) ? lp > ld : 1; /* XXX should consider '!' and '/' ? */
2645                 } else {
2646 #ifdef NEED_DEBUG_HERE
2647                         ast_log(LOG_NOTICE,"return (0) when ld(%d) > 0 && pattern(%s) != data(%s)\n", ld, pattern, data);
2648 #endif
2649                         return 0;
2650                 }
2651         }
2652         pattern++; /* skip leading _ */
2653         /*
2654          * XXX below we stop at '/' which is a separator for the CID info. However we should
2655          * not store '/' in the pattern at all. When we insure it, we can remove the checks.
2656          */
2657         while (*data && *pattern && *pattern != '/') {
2658                 const char *end;
2659
2660                 if (*data == '-') { /* skip '-' in data (just a separator) */
2661                         data++;
2662                         continue;
2663                 }
2664                 switch (toupper(*pattern)) {
2665                 case '[':       /* a range */
2666                         end = strchr(pattern+1, ']'); /* XXX should deal with escapes ? */
2667                         if (end == NULL) {
2668                                 ast_log(LOG_WARNING, "Wrong usage of [] in the extension\n");
2669                                 return 0;       /* unconditional failure */
2670                         }
2671                         for (pattern++; pattern != end; pattern++) {
2672                                 if (pattern+2 < end && pattern[1] == '-') { /* this is a range */
2673                                         if (*data >= pattern[0] && *data <= pattern[2])
2674                                                 break;  /* match found */
2675                                         else {
2676                                                 pattern += 2; /* skip a total of 3 chars */
2677                                                 continue;
2678                                         }
2679                                 } else if (*data == pattern[0])
2680                                         break;  /* match found */
2681                         }
2682                         if (pattern == end) {
2683 #ifdef NEED_DEBUG_HERE
2684                                 ast_log(LOG_NOTICE,"return (0) when pattern==end\n");
2685 #endif
2686                                 return 0;
2687                         }
2688                         pattern = end;  /* skip and continue */
2689                         break;
2690                 case 'N':
2691                         if (*data < '2' || *data > '9') {
2692 #ifdef NEED_DEBUG_HERE
2693                                 ast_log(LOG_NOTICE,"return (0) N is matched\n");
2694 #endif
2695                                 return 0;
2696                         }
2697                         break;
2698                 case 'X':
2699                         if (*data < '0' || *data > '9') {
2700 #ifdef NEED_DEBUG_HERE
2701                                 ast_log(LOG_NOTICE,"return (0) X is matched\n");
2702 #endif
2703                                 return 0;
2704                         }
2705                         break;
2706                 case 'Z':
2707                         if (*data < '1' || *data > '9') {
2708 #ifdef NEED_DEBUG_HERE
2709                                 ast_log(LOG_NOTICE,"return (0) Z is matched\n");
2710 #endif
2711                                 return 0;
2712                         }
2713                         break;
2714                 case '.':       /* Must match, even with more digits */
2715 #ifdef NEED_DEBUG_HERE
2716                         ast_log(LOG_NOTICE, "return (1) when '.' is matched\n");
2717 #endif
2718                         return 1;
2719                 case '!':       /* Early match */
2720 #ifdef NEED_DEBUG_HERE
2721                         ast_log(LOG_NOTICE, "return (2) when '!' is matched\n");
2722 #endif
2723                         return 2;
2724                 case ' ':
2725                 case '-':       /* Ignore these in patterns */
2726                         data--; /* compensate the final data++ */
2727                         break;
2728                 default:
2729                         if (*data != *pattern) {
2730 #ifdef NEED_DEBUG_HERE
2731                                 ast_log(LOG_NOTICE, "return (0) when *data(%c) != *pattern(%c)\n", *data, *pattern);
2732 #endif
2733                                 return 0;
2734                         }
2735                 }
2736                 data++;
2737                 pattern++;
2738         }
2739         if (*data)                      /* data longer than pattern, no match */ {
2740 #ifdef NEED_DEBUG_HERE
2741                 ast_log(LOG_NOTICE, "return (0) when data longer than pattern\n");
2742 #endif
2743                 return 0;
2744         }
2745
2746         /*
2747          * match so far, but ran off the end of the data.
2748          * Depending on what is next, determine match or not.
2749          */
2750         if (*pattern == '\0' || *pattern == '/') {      /* exact match */
2751 #ifdef NEED_DEBUG_HERE
2752                 ast_log(LOG_NOTICE, "at end, return (%d) in 'exact match'\n", (mode==E_MATCHMORE) ? 0 : 1);
2753 #endif
2754                 return (mode == E_MATCHMORE) ? 0 : 1;   /* this is a failure for E_MATCHMORE */
2755         } else if (*pattern == '!')     {               /* early match */
2756 #ifdef NEED_DEBUG_HERE
2757                 ast_log(LOG_NOTICE, "at end, return (2) when '!' is matched\n");
2758 #endif
2759                 return 2;
2760         } else {                                                /* partial match */
2761 #ifdef NEED_DEBUG_HERE
2762                 ast_log(LOG_NOTICE, "at end, return (%d) which deps on E_MATCH\n", (mode == E_MATCH) ? 0 : 1);
2763 #endif
2764                 return (mode == E_MATCH) ? 0 : 1;       /* this is a failure for E_MATCH */
2765         }
2766 }
2767
2768 /*
2769  * Wrapper around _extension_match_core() to do performance measurement
2770  * using the profiling code.
2771  */
2772 static int extension_match_core(const char *pattern, const char *data, enum ext_match_t mode)
2773 {
2774         int i;
2775         static int prof_id = -2;        /* marker for 'unallocated' id */
2776         if (prof_id == -2) {
2777                 prof_id = ast_add_profile("ext_match", 0);
2778         }
2779         ast_mark(prof_id, 1);
2780         i = _extension_match_core(ast_strlen_zero(pattern) ? "" : pattern, ast_strlen_zero(data) ? "" : data, mode);
2781         ast_mark(prof_id, 0);
2782         return i;
2783 }
2784
2785 int ast_extension_match(const char *pattern, const char *data)
2786 {
2787         return extension_match_core(pattern, data, E_MATCH);
2788 }
2789
2790 int ast_extension_close(const char *pattern, const char *data, int needmore)
2791 {
2792         if (needmore != E_MATCHMORE && needmore != E_CANMATCH)
2793                 ast_log(LOG_WARNING, "invalid argument %d\n", needmore);
2794         return extension_match_core(pattern, data, needmore);
2795 }
2796
2797 struct fake_context /* this struct is purely for matching in the hashtab */
2798 {
2799         ast_rwlock_t lock;
2800         struct ast_exten *root;
2801         struct ast_hashtab *root_table;
2802         struct match_char *pattern_tree;
2803         struct ast_context *next;
2804         struct ast_include *includes;
2805         struct ast_ignorepat *ignorepats;
2806         const char *registrar;
2807         int refcount;
2808         AST_LIST_HEAD_NOLOCK(, ast_sw) alts;
2809         ast_mutex_t macrolock;
2810         char name[256];
2811 };
2812
2813 struct ast_context *ast_context_find(const char *name)
2814 {
2815         struct ast_context *tmp;
2816         struct fake_context item;
2817
2818         if (!name) {
2819                 return NULL;
2820         }
2821         ast_rdlock_contexts();
2822         if (contexts_table) {
2823                 ast_copy_string(item.name, name, sizeof(item.name));
2824                 tmp = ast_hashtab_lookup(contexts_table, &item);
2825         } else {
2826                 tmp = NULL;
2827                 while ((tmp = ast_walk_contexts(tmp))) {
2828                         if (!strcasecmp(name, tmp->name)) {
2829                                 break;
2830                         }
2831                 }
2832         }
2833         ast_unlock_contexts();
2834         return tmp;
2835 }
2836
2837 #define STATUS_NO_CONTEXT       1
2838 #define STATUS_NO_EXTENSION     2
2839 #define STATUS_NO_PRIORITY      3
2840 #define STATUS_NO_LABEL         4
2841 #define STATUS_SUCCESS          5
2842
2843 static int matchcid(const char *cidpattern, const char *callerid)
2844 {
2845         /* If the Caller*ID pattern is empty, then we're matching NO Caller*ID, so
2846            failing to get a number should count as a match, otherwise not */
2847
2848         if (ast_strlen_zero(callerid)) {
2849                 return ast_strlen_zero(cidpattern) ? 1 : 0;
2850         }
2851
2852         return ast_extension_match(cidpattern, callerid);
2853 }
2854
2855 struct ast_exten *pbx_find_extension(struct ast_channel *chan,
2856         struct ast_context *bypass, struct pbx_find_info *q,
2857         const char *context, const char *exten, int priority,
2858         const char *label, const char *callerid, enum ext_match_t action)
2859 {
2860         int x, res;
2861         struct ast_context *tmp = NULL;
2862         struct ast_exten *e = NULL, *eroot = NULL;
2863         struct ast_include *i = NULL;
2864         struct ast_sw *sw = NULL;
2865         struct ast_exten pattern = {NULL, };
2866         struct scoreboard score = {0, };
2867         struct ast_str *tmpdata = NULL;
2868
2869         pattern.label = label;
2870         pattern.priority = priority;
2871 #ifdef NEED_DEBUG_HERE
2872         ast_log(LOG_NOTICE, "Looking for cont/ext/prio/label/action = %s/%s/%d/%s/%d\n", context, exten, priority, label, (int) action);
2873 #endif
2874
2875         /* Initialize status if appropriate */
2876         if (q->stacklen == 0) {
2877                 q->status = STATUS_NO_CONTEXT;
2878                 q->swo = NULL;
2879                 q->data = NULL;
2880                 q->foundcontext = NULL;
2881         } else if (q->stacklen >= AST_PBX_MAX_STACK) {
2882                 ast_log(LOG_WARNING, "Maximum PBX stack exceeded\n");
2883                 return NULL;
2884         }
2885
2886         /* Check first to see if we've already been checked */
2887         for (x = 0; x < q->stacklen; x++) {
2888                 if (!strcasecmp(q->incstack[x], context))
2889                         return NULL;
2890         }
2891
2892         if (bypass) { /* bypass means we only look there */
2893                 tmp = bypass;
2894         } else {      /* look in contexts */
2895                 tmp = find_context(context);
2896                 if (!tmp) {
2897                         return NULL;
2898                 }
2899         }
2900
2901         if (q->status < STATUS_NO_EXTENSION)
2902                 q->status = STATUS_NO_EXTENSION;
2903
2904         /* Do a search for matching extension */
2905
2906         eroot = NULL;
2907         score.total_specificity = 0;
2908         score.exten = 0;
2909         score.total_length = 0;
2910         if (!tmp->pattern_tree && tmp->root_table) {
2911                 create_match_char_tree(tmp);
2912 #ifdef NEED_DEBUG
2913                 ast_debug(1, "Tree Created in context %s:\n", context);
2914                 log_match_char_tree(tmp->pattern_tree," ");
2915 #endif
2916         }
2917 #ifdef NEED_DEBUG
2918         ast_log(LOG_NOTICE, "The Trie we are searching in:\n");
2919         log_match_char_tree(tmp->pattern_tree, "::  ");
2920 #endif
2921
2922         do {
2923                 if (!ast_strlen_zero(overrideswitch)) {
2924                         char *osw = ast_strdupa(overrideswitch), *name;
2925                         struct ast_switch *asw;
2926                         ast_switch_f *aswf = NULL;
2927                         char *datap;
2928                         int eval = 0;
2929
2930                         name = strsep(&osw, "/");
2931                         asw = pbx_findswitch(name);
2932
2933                         if (!asw) {
2934                                 ast_log(LOG_WARNING, "No such switch '%s'\n", name);
2935                                 break;
2936                         }
2937
2938                         if (osw && strchr(osw, '$')) {
2939                                 eval = 1;
2940                         }
2941
2942                         if (eval && !(tmpdata = ast_str_thread_get(&switch_data, 512))) {
2943                                 ast_log(LOG_WARNING, "Can't evaluate overrideswitch?!\n");
2944                                 break;
2945                         } else if (eval) {
2946                                 /* Substitute variables now */
2947                                 pbx_substitute_variables_helper(chan, osw, ast_str_buffer(tmpdata), ast_str_size(tmpdata));
2948                                 datap = ast_str_buffer(tmpdata);
2949                         } else {
2950                                 datap = osw;
2951                         }
2952
2953                         /* equivalent of extension_match_core() at the switch level */
2954                         if (action == E_CANMATCH)
2955                                 aswf = asw->canmatch;
2956                         else if (action == E_MATCHMORE)
2957                                 aswf = asw->matchmore;
2958                         else /* action == E_MATCH */
2959                                 aswf = asw->exists;
2960                         if (!aswf) {
2961                                 res = 0;
2962                         } else {
2963                                 if (chan) {
2964                                         ast_autoservice_start(chan);
2965                                 }
2966                                 res = aswf(chan, context, exten, priority, callerid, datap);
2967                                 if (chan) {
2968                                         ast_autoservice_stop(chan);
2969                                 }
2970                         }
2971                         if (res) {      /* Got a match */
2972                                 q->swo = asw;
2973                                 q->data = datap;
2974                                 q->foundcontext = context;
2975                                 /* XXX keep status = STATUS_NO_CONTEXT ? */
2976                                 return NULL;
2977                         }
2978                 }
2979         } while (0);
2980
2981         if (extenpatternmatchnew) {
2982                 new_find_extension(exten, &score, tmp->pattern_tree, 0, 0, callerid, label, action);
2983                 eroot = score.exten;
2984
2985                 if (score.last_char == '!' && action == E_MATCHMORE) {
2986                         /* We match an extension ending in '!'.
2987                          * The decision in this case is final and is NULL (no match).
2988                          */
2989 #ifdef NEED_DEBUG_HERE
2990                         ast_log(LOG_NOTICE,"Returning MATCHMORE NULL with exclamation point.\n");
2991 #endif
2992                         return NULL;
2993                 }
2994
2995                 if (!eroot && (action == E_CANMATCH || action == E_MATCHMORE) && score.canmatch_exten) {
2996                         q->status = STATUS_SUCCESS;
2997 #ifdef NEED_DEBUG_HERE
2998                         ast_log(LOG_NOTICE,"Returning CANMATCH exten %s\n", score.canmatch_exten->exten);
2999 #endif
3000                         return score.canmatch_exten;
3001                 }
3002
3003                 if ((action == E_MATCHMORE || action == E_CANMATCH)  && eroot) {
3004                         if (score.node) {
3005                                 struct ast_exten *z = trie_find_next_match(score.node);
3006                                 if (z) {
3007 #ifdef NEED_DEBUG_HERE
3008                                         ast_log(LOG_NOTICE,"Returning CANMATCH/MATCHMORE next_match exten %s\n", z->exten);
3009 #endif
3010                                 } else {
3011                                         if (score.canmatch_exten) {
3012 #ifdef NEED_DEBUG_HERE
3013                                                 ast_log(LOG_NOTICE,"Returning CANMATCH/MATCHMORE canmatchmatch exten %s(%p)\n", score.canmatch_exten->exten, score.canmatch_exten);
3014 #endif
3015                                                 return score.canmatch_exten;
3016                                         } else {
3017 #ifdef NEED_DEBUG_HERE
3018                                                 ast_log(LOG_NOTICE,"Returning CANMATCH/MATCHMORE next_match exten NULL\n");
3019 #endif
3020                                         }
3021                                 }
3022                                 return z;
3023                         }
3024 #ifdef NEED_DEBUG_HERE
3025                         ast_log(LOG_NOTICE, "Returning CANMATCH/MATCHMORE NULL (no next_match)\n");
3026 #endif
3027                         return NULL;  /* according to the code, complete matches are null matches in MATCHMORE mode */
3028                 }
3029
3030                 if (eroot) {
3031                         /* found entry, now look for the right priority */
3032                         if (q->status < STATUS_NO_PRIORITY)
3033                                 q->status = STATUS_NO_PRIORITY;
3034                         e = NULL;
3035                         if (action == E_FINDLABEL && label ) {
3036                                 if (q->status < STATUS_NO_LABEL)
3037                                         q->status = STATUS_NO_LABEL;
3038                                 e = ast_hashtab_lookup(eroot->peer_label_table, &pattern);
3039                         } else {
3040                                 e = ast_hashtab_lookup(eroot->peer_table, &pattern);
3041                         }
3042                         if (e) {        /* found a valid match */
3043                                 q->status = STATUS_SUCCESS;
3044                                 q->foundcontext = context;
3045 #ifdef NEED_DEBUG_HERE
3046                                 ast_log(LOG_NOTICE,"Returning complete match of exten %s\n", e->exten);
3047 #endif
3048                                 return e;
3049                         }
3050                 }
3051         } else {   /* the old/current default exten pattern match algorithm */
3052
3053                 /* scan the list trying to match extension and CID */
3054                 eroot = NULL;
3055                 while ( (eroot = ast_walk_context_extensions(tmp, eroot)) ) {
3056                         int match = extension_match_core(eroot->exten, exten, action);
3057                         /* 0 on fail, 1 on match, 2 on earlymatch */
3058
3059                         if (!match || (eroot->matchcid && !matchcid(eroot->cidmatch, callerid)))
3060                                 continue;       /* keep trying */
3061                         if (match == 2 && action == E_MATCHMORE) {
3062                                 /* We match an extension ending in '!'.
3063                                  * The decision in this case is final and is NULL (no match).
3064                                  */
3065                                 return NULL;
3066                         }
3067                         /* found entry, now look for the right priority */
3068                         if (q->status < STATUS_NO_PRIORITY)
3069                                 q->status = STATUS_NO_PRIORITY;
3070                         e = NULL;
3071                         if (action == E_FINDLABEL && label ) {
3072                                 if (q->status < STATUS_NO_LABEL)
3073                                         q->status = STATUS_NO_LABEL;
3074                                 e = ast_hashtab_lookup(eroot->peer_label_table, &pattern);
3075                         } else {
3076                                 e = ast_hashtab_lookup(eroot->peer_table, &pattern);
3077                         }
3078                         if (e) {        /* found a valid match */
3079                                 q->status = STATUS_SUCCESS;
3080                                 q->foundcontext = context;
3081                                 return e;
3082                         }
3083                 }
3084         }
3085
3086         /* Check alternative switches */
3087         AST_LIST_TRAVERSE(&tmp->alts, sw, list) {
3088                 struct ast_switch *asw = pbx_findswitch(sw->name);
3089                 ast_switch_f *aswf = NULL;
3090                 char *datap;
3091
3092                 if (!asw) {
3093                         ast_log(LOG_WARNING, "No such switch '%s'\n", sw->name);
3094                         continue;
3095                 }
3096
3097                 /* Substitute variables now */
3098                 if (sw->eval) {
3099                         if (!(tmpdata = ast_str_thread_get(&switch_data, 512))) {
3100                                 ast_log(LOG_WARNING, "Can't evaluate switch?!\n");
3101                                 continue;
3102                         }
3103                         pbx_substitute_variables_helper(chan, sw->data, ast_str_buffer(tmpdata), ast_str_size(tmpdata));
3104                 }
3105
3106                 /* equivalent of extension_match_core() at the switch level */
3107                 if (action == E_CANMATCH)
3108                         aswf = asw->canmatch;
3109                 else if (action == E_MATCHMORE)
3110                         aswf = asw->matchmore;
3111                 else /* action == E_MATCH */
3112                         aswf = asw->exists;
3113                 datap = sw->eval ? ast_str_buffer(tmpdata) : sw->data;
3114                 if (!aswf)
3115                         res = 0;
3116                 else {
3117                         if (chan)
3118                                 ast_autoservice_start(chan);
3119                         res = aswf(chan, context, exten, priority, callerid, datap);
3120                         if (chan)
3121                                 ast_autoservice_stop(chan);
3122                 }
3123                 if (res) {      /* Got a match */
3124                         q->swo = asw;
3125                         q->data = datap;
3126                         q->foundcontext = context;
3127                         /* XXX keep status = STATUS_NO_CONTEXT ? */
3128                         return NULL;
3129                 }
3130         }
3131         q->incstack[q->stacklen++] = tmp->name; /* Setup the stack */
3132         /* Now try any includes we have in this context */
3133         for (i = tmp->includes; i; i = i->next) {
3134                 if (include_valid(i)) {
3135                         if ((e = pbx_find_extension(chan, bypass, q, i->rname, exten, priority, label, callerid, action))) {
3136 #ifdef NEED_DEBUG_HERE
3137                                 ast_log(LOG_NOTICE,"Returning recursive match of %s\n", e->exten);
3138 #endif
3139                                 return e;
3140                         }
3141                         if (q->swo)
3142                                 return NULL;
3143                 }
3144         }
3145         return NULL;
3146 }
3147
3148 /*!
3149  * \brief extract offset:length from variable name.
3150  * \return 1 if there is a offset:length part, which is
3151  * trimmed off (values go into variables)
3152  */
3153 static int parse_variable_name(char *var, int *offset, int *length, int *isfunc)
3154 {
3155         int parens = 0;
3156
3157         *offset = 0;
3158         *length = INT_MAX;
3159         *isfunc = 0;
3160         for (; *var; var++) {
3161                 if (*var == '(') {
3162                         (*isfunc)++;
3163                         parens++;
3164                 } else if (*var == ')') {
3165                         parens--;
3166                 } else if (*var == ':' && parens == 0) {
3167                         *var++ = '\0';
3168                         sscanf(var, "%30d:%30d", offset, length);
3169                         return 1; /* offset:length valid */
3170                 }
3171         }
3172         return 0;
3173 }
3174
3175 /*!
3176  *\brief takes a substring. It is ok to call with value == workspace.
3177  * \param value
3178  * \param offset < 0 means start from the end of the string and set the beginning
3179  *   to be that many characters back.
3180  * \param length is the length of the substring, a value less than 0 means to leave
3181  * that many off the end.
3182  * \param workspace
3183  * \param workspace_len
3184  * Always return a copy in workspace.
3185  */
3186 static char *substring(const char *value, int offset, int length, char *workspace, size_t workspace_len)
3187 {
3188         char *ret = workspace;
3189         int lr; /* length of the input string after the copy */
3190
3191         ast_copy_string(workspace, value, workspace_len); /* always make a copy */
3192
3193         lr = strlen(ret); /* compute length after copy, so we never go out of the workspace */
3194
3195         /* Quick check if no need to do anything */
3196         if (offset == 0 && length >= lr)        /* take the whole string */
3197                 return ret;
3198
3199         if (offset < 0) {       /* translate negative offset into positive ones */
3200                 offset = lr + offset;
3201                 if (offset < 0) /* If the negative offset was greater than the length of the string, just start at the beginning */
3202                         offset = 0;
3203         }
3204
3205         /* too large offset result in empty string so we know what to return */
3206         if (offset >= lr)
3207                 return ret + lr;        /* the final '\0' */
3208
3209         ret += offset;          /* move to the start position */
3210         if (length >= 0 && length < lr - offset)        /* truncate if necessary */
3211                 ret[length] = '\0';
3212         else if (length < 0) {
3213                 if (lr > offset - length) /* After we remove from the front and from the rear, is there anything left? */
3214                         ret[lr + length - offset] = '\0';
3215                 else
3216                         ret[0] = '\0';
3217         }
3218
3219         return ret;
3220 }
3221
3222 static const char *ast_str_substring(struct ast_str *value, int offset, int length)
3223 {
3224         int lr; /* length of the input string after the copy */
3225
3226         lr = ast_str_strlen(value); /* compute length after copy, so we never go out of the workspace */
3227
3228         /* Quick check if no need to do anything */
3229         if (offset == 0 && length >= lr)        /* take the whole string */
3230                 return ast_str_buffer(value);
3231
3232         if (offset < 0) {       /* translate negative offset into positive ones */
3233                 offset = lr + offset;
3234                 if (offset < 0) /* If the negative offset was greater than the length of the string, just start at the beginning */
3235                         offset = 0;
3236         }
3237
3238         /* too large offset result in empty string so we know what to return */
3239         if (offset >= lr) {
3240                 ast_str_reset(value);
3241                 return ast_str_buffer(value);
3242         }
3243
3244         if (offset > 0) {
3245                 /* Go ahead and chop off the beginning */
3246                 memmove(ast_str_buffer(value), ast_str_buffer(value) + offset, ast_str_strlen(value) - offset + 1);
3247                 lr -= offset;
3248         }
3249
3250         if (length >= 0 && length < lr) {       /* truncate if necessary */
3251                 char *tmp = ast_str_buffer(value);
3252                 tmp[length] = '\0';
3253                 ast_str_update(value);
3254         } else if (length < 0) {
3255                 if (lr > -length) { /* After we remove from the front and from the rear, is there anything left? */
3256                         char *tmp = ast_str_buffer(value);
3257                         tmp[lr + length] = '\0';
3258                         ast_str_update(value);
3259                 } else {
3260                         ast_str_reset(value);
3261                 }
3262         } else {
3263                 /* Nothing to do, but update the buffer length */
3264                 ast_str_update(value);
3265         }
3266
3267         return ast_str_buffer(value);
3268 }
3269
3270 /*! \brief  Support for Asterisk built-in variables in the dialplan
3271
3272 \note   See also
3273         - \ref AstVar   Channel variables
3274         - \ref AstCauses The HANGUPCAUSE variable
3275  */
3276 void pbx_retrieve_variable(struct ast_channel *c, const char *var, char **ret, char *workspace, int workspacelen, struct varshead *headp)
3277 {
3278         struct ast_str *str = ast_str_create(16);
3279         const char *cret;
3280
3281         cret = ast_str_retrieve_variable(&str, 0, c, headp, var);
3282         ast_copy_string(workspace, ast_str_buffer(str), workspacelen);
3283         *ret = cret ? workspace : NULL;
3284         ast_free(str);
3285 }
3286
3287 const char *ast_str_retrieve_variable(struct ast_str **str, ssize_t maxlen, struct ast_channel *c, struct varshead *headp, const char *var)
3288 {
3289         const char not_found = '\0';
3290         char *tmpvar;
3291         const char *ret;
3292         const char *s;  /* the result */
3293         int offset, length;
3294         int i, need_substring;
3295         struct varshead *places[2] = { headp, &globals };       /* list of places where we may look */
3296         char workspace[20];
3297
3298         if (c) {
3299                 ast_channel_lock(c);
3300   &n