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