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