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