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