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