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