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