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