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