PhabricatorCursorPagedPolicyAwareQuery.php 89.2 KB
Newer Older
1 2 3
<?php

/**
4 5
 * A query class which uses cursor-based paging. This paging is much more
 * performant than offset-based paging in the presence of policy filtering.
6
 *
7
 * @task cursors Query Cursors
8
 * @task clauses Building Query Clauses
9
 * @task appsearch Integration with ApplicationSearch
10
 * @task customfield Integration with CustomField
11
 * @task paging Paging
epriestley's avatar
epriestley committed
12
 * @task order Result Ordering
13
 * @task edgelogic Working with Edge Logic
14
 * @task spaces Working with Spaces
15
 */
16 17
abstract class PhabricatorCursorPagedPolicyAwareQuery
  extends PhabricatorPolicyAwareQuery {
18

19 20 21
  private $externalCursorString;
  private $internalCursorObject;
  private $isQueryOrderReversed = false;
22
  private $rawCursorRow;
23

24
  private $applicationSearchConstraints = array();
25
  private $internalPaging;
epriestley's avatar
epriestley committed
26
  private $orderVector;
27
  private $groupVector;
28
  private $builtinOrder;
29
  private $edgeLogicConstraints = array();
30
  private $edgeLogicConstraintsAreValid = false;
31
  private $spacePHIDs;
epriestley's avatar
epriestley committed
32
  private $spaceIsArchived;
33
  private $ngrams = array();
34
  private $ferretEngine;
35 36 37
  private $ferretTokens = array();
  private $ferretTables = array();
  private $ferretQuery;
38
  private $ferretMetadata = array();
39

40 41 42 43
  const FULLTEXT_RANK = '_ft_rank';
  const FULLTEXT_MODIFIED = '_ft_epochModified';
  const FULLTEXT_CREATED = '_ft_epochCreated';

44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
/* -(  Cursors  )------------------------------------------------------------ */

  protected function newExternalCursorStringForResult($object) {
    if (!($object instanceof LiskDAO)) {
      throw new Exception(
        pht(
          'Expected to be passed a result object of class "LiskDAO" in '.
          '"newExternalCursorStringForResult()", actually passed "%s". '.
          'Return storage objects from "loadPage()" or override '.
          '"newExternalCursorStringForResult()".',
          phutil_describe_type($object)));
    }

    return (string)$object->getID();
  }

  protected function newInternalCursorFromExternalCursor($cursor) {
    $viewer = $this->getViewer();

    $query = newv(get_class($this), array());

    $query
      ->setParentQuery($this)
67
      ->setViewer($viewer);
68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83

    // We're copying our order vector to the subquery so that the subquery
    // knows it should generate any supplemental information required by the
    // ordering.

    // For example, Phriction documents may be ordered by title, but the title
    // isn't a column in the "document" table: the query must JOIN the
    // "content" table to perform the ordering. Passing the ordering to the
    // subquery tells it that we need it to do that JOIN and attach relevant
    // paging information to the internal cursor object.

    // We only expect to load a single result, so the actual result order does
    // not matter. We only want the internal cursor for that result to look
    // like a cursor this parent query would generate.
    $query->setOrderVector($this->getOrderVector());

84 85
    $this->applyExternalCursorConstraintsToQuery($query, $cursor);

86 87 88 89 90 91 92
    // If we have a Ferret fulltext query, copy it to the subquery so that we
    // generate ranking columns appropriately, and compute the correct object
    // ranking score for the current query.
    if ($this->ferretEngine) {
      $query->withFerretConstraint($this->ferretEngine, $this->ferretTokens);
    }

93 94 95 96 97 98
    // We're executing the subquery normally to make sure the viewer can
    // actually see the object, and that it's a completely valid object which
    // passes all filtering and policy checks. You aren't allowed to use an
    // object you can't see as a cursor, since this can leak information.
    $result = $query->executeOne();
    if (!$result) {
99
      $this->throwCursorException(
100
        pht(
101
          'Cursor "%s" does not identify a valid object in query "%s".',
102
          $cursor,
103
          get_class($this)));
104
    }
105

106
    // Now that we made sure the viewer can actually see the object the
107
    // external cursor identifies, return the internal cursor the query
108 109
    // generated as a side effect while loading the object.
    return $query->getInternalCursorObject();
110 111
  }

112
  final protected function throwCursorException($message) {
113
    throw new PhabricatorInvalidQueryCursorException($message);
114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136
  }

  protected function applyExternalCursorConstraintsToQuery(
    PhabricatorCursorPagedPolicyAwareQuery $subquery,
    $cursor) {
    $subquery->withIDs(array($cursor));
  }

  protected function newPagingMapFromCursorObject(
    PhabricatorQueryCursor $cursor,
    array $keys) {

    $object = $cursor->getObject();

    return $this->newPagingMapFromPartialObject($object);
  }

  protected function newPagingMapFromPartialObject($object) {
    return array(
      'id' => (int)$object->getID(),
    );
  }

137 138
  final private function getExternalCursorStringForResult($object) {
    $cursor = $this->newExternalCursorStringForResult($object);
139

140 141 142 143 144 145 146
    if (!is_string($cursor)) {
      throw new Exception(
        pht(
          'Expected "newExternalCursorStringForResult()"  in class "%s" to '.
          'return a string, but got "%s".',
          get_class($this),
          phutil_describe_type($cursor)));
147
    }
148 149 150 151

    return $cursor;
  }

152
  final protected function getExternalCursorString() {
153 154 155 156 157 158
    return $this->externalCursorString;
  }

  final private function setExternalCursorString($external_cursor) {
    $this->externalCursorString = $external_cursor;
    return $this;
159 160
  }

161
  final protected function getIsQueryOrderReversed() {
162 163 164
    return $this->isQueryOrderReversed;
  }

165
  final protected function setIsQueryOrderReversed($is_reversed) {
166
    $this->isQueryOrderReversed = $is_reversed;
167 168 169
    return $this;
  }

170 171
  final private function getInternalCursorObject() {
    return $this->internalCursorObject;
172 173
  }

174 175 176
  final private function setInternalCursorObject(
    PhabricatorQueryCursor $cursor) {
    $this->internalCursorObject = $cursor;
177 178 179
    return $this;
  }

180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212
  final private function getInternalCursorFromExternalCursor(
    $cursor_string) {

    $cursor_object = $this->newInternalCursorFromExternalCursor($cursor_string);

    if (!($cursor_object instanceof PhabricatorQueryCursor)) {
      throw new Exception(
        pht(
          'Expected "newInternalCursorFromExternalCursor()" to return an '.
          'object of class "PhabricatorQueryCursor", but got "%s" (in '.
          'class "%s").',
          phutil_describe_type($cursor_object),
          get_class($this)));
    }

    return $cursor_object;
  }

  final private function getPagingMapFromCursorObject(
    PhabricatorQueryCursor $cursor,
    array $keys) {

    $map = $this->newPagingMapFromCursorObject($cursor, $keys);

    if (!is_array($map)) {
      throw new Exception(
        pht(
          'Expected "newPagingMapFromCursorObject()" to return a map of '.
          'paging values, but got "%s" (in class "%s").',
          phutil_describe_type($map),
          get_class($this)));
    }

213
    if ($this->supportsFerretEngine()) {
214
      if ($this->hasFerretOrder()) {
215 216 217 218 219 220 221 222 223 224 225
        $map += array(
          'rank' =>
            $cursor->getRawRowProperty(self::FULLTEXT_RANK),
          'fulltext-modified' =>
            $cursor->getRawRowProperty(self::FULLTEXT_MODIFIED),
          'fulltext-created' =>
            $cursor->getRawRowProperty(self::FULLTEXT_CREATED),
        );
      }
    }

226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247
    foreach ($keys as $key) {
      if (!array_key_exists($key, $map)) {
        throw new Exception(
          pht(
            'Map returned by "newPagingMapFromCursorObject()" in class "%s" '.
            'omits required key "%s".',
            get_class($this),
            $key));
      }
    }

    return $map;
  }

  final protected function nextPage(array $page) {
    if (!$page) {
      return;
    }

    $cursor = id(new PhabricatorQueryCursor())
      ->setObject(last($page));

248 249 250 251
    if ($this->rawCursorRow) {
      $cursor->setRawRow($this->rawCursorRow);
    }

252
    $this->setInternalCursorObject($cursor);
253 254
  }

255 256 257 258 259 260 261 262 263 264 265 266
  final public function getFerretMetadata() {
    if (!$this->supportsFerretEngine()) {
      throw new Exception(
        pht(
          'Unable to retrieve Ferret engine metadata, this class ("%s") does '.
          'not support the Ferret engine.',
          get_class($this)));
    }

    return $this->ferretMetadata;
  }

267 268 269 270 271 272
  protected function loadStandardPage(PhabricatorLiskDAO $table) {
    $rows = $this->loadStandardPageRows($table);
    return $table->loadAllFromArray($rows);
  }

  protected function loadStandardPageRows(PhabricatorLiskDAO $table) {
epriestley's avatar
epriestley committed
273
    $conn = $table->establishConnection('r');
274 275 276 277 278 279 280 281
    return $this->loadStandardPageRowsWithConnection(
      $conn,
      $table->getTableName());
  }

  protected function loadStandardPageRowsWithConnection(
    AphrontDatabaseConnection $conn,
    $table_name) {
epriestley's avatar
epriestley committed
282

283 284 285 286 287 288 289 290 291 292 293 294
    $query = $this->buildStandardPageQuery($conn, $table_name);

    $rows = queryfx_all($conn, '%Q', $query);
    $rows = $this->didLoadRawRows($rows);

    return $rows;
  }

  protected function buildStandardPageQuery(
    AphrontDatabaseConnection $conn,
    $table_name) {

295 296 297 298 299 300 301
    $table_alias = $this->getPrimaryTableAlias();
    if ($table_alias === null) {
      $table_alias = qsprintf($conn, '');
    } else {
      $table_alias = qsprintf($conn, '%T', $table_alias);
    }

302
    return qsprintf(
epriestley's avatar
epriestley committed
303 304 305
      $conn,
      '%Q FROM %T %Q %Q %Q %Q %Q %Q %Q',
      $this->buildSelectClause($conn),
306
      $table_name,
307
      $table_alias,
epriestley's avatar
epriestley committed
308 309 310 311 312 313
      $this->buildJoinClause($conn),
      $this->buildWhereClause($conn),
      $this->buildGroupClause($conn),
      $this->buildHavingClause($conn),
      $this->buildOrderClause($conn),
      $this->buildLimitClause($conn));
314 315 316
  }

  protected function didLoadRawRows(array $rows) {
317 318
    $this->rawCursorRow = last($rows);

319 320 321 322 323 324 325
    if ($this->ferretEngine) {
      foreach ($rows as $row) {
        $phid = $row['phid'];

        $metadata = id(new PhabricatorFerretMetadata())
          ->setPHID($phid)
          ->setEngine($this->ferretEngine)
326
          ->setRelevance(idx($row, self::FULLTEXT_RANK));
327 328 329

        $this->ferretMetadata[$phid] = $metadata;

330 331 332
        unset($row[self::FULLTEXT_RANK]);
        unset($row[self::FULLTEXT_MODIFIED]);
        unset($row[self::FULLTEXT_CREATED]);
333 334 335
      }
    }

336
    return $rows;
337 338
  }

339
  final protected function buildLimitClause(AphrontDatabaseConnection $conn) {
340 341 342
    if ($this->shouldLimitResults()) {
      $limit = $this->getRawResultLimit();
      if ($limit) {
343
        return qsprintf($conn, 'LIMIT %d', $limit);
344
      }
345
    }
346

347
    return qsprintf($conn, '');
348 349 350 351
  }

  protected function shouldLimitResults() {
    return true;
352 353
  }

354
  final protected function didLoadResults(array $results) {
355
    if ($this->getIsQueryOrderReversed()) {
356 357
      $results = array_reverse($results, $preserve_keys = true);
    }
358

359 360 361
    return $results;
  }

362
  final public function executeWithCursorPager(AphrontCursorPagerView $pager) {
363 364 365
    $limit = $pager->getPageSize();

    $this->setLimit($limit + 1);
366

367 368
    if (strlen($pager->getAfterID())) {
      $this->setExternalCursorString($pager->getAfterID());
369
    } else if ($pager->getBeforeID()) {
370 371
      $this->setExternalCursorString($pager->getBeforeID());
      $this->setIsQueryOrderReversed(true);
372 373 374
    }

    $results = $this->execute();
375
    $count = count($results);
376 377

    $sliced_results = $pager->sliceResults($results);
378
    if ($sliced_results) {
379 380 381 382

      // If we have results, generate external-facing cursors from the visible
      // results. This stops us from leaking any internal details about objects
      // which we loaded but which were not visible to the viewer.
383 384

      if ($pager->getBeforeID() || ($count > $limit)) {
385 386 387
        $last_object = last($sliced_results);
        $cursor = $this->getExternalCursorStringForResult($last_object);
        $pager->setNextPageID($cursor);
388 389 390
      }

      if ($pager->getAfterID() ||
391
         ($pager->getBeforeID() && ($count > $limit))) {
392 393 394
        $head_object = head($sliced_results);
        $cursor = $this->getExternalCursorStringForResult($head_object);
        $pager->setPrevPageID($cursor);
395
      }
396 397 398 399 400
    }

    return $sliced_results;
  }

401

402 403 404 405 406 407 408 409 410 411 412 413 414 415
  /**
   * Return the alias this query uses to identify the primary table.
   *
   * Some automatic query constructions may need to be qualified with a table
   * alias if the query performs joins which make column names ambiguous. If
   * this is the case, return the alias for the primary table the query
   * uses; generally the object table which has `id` and `phid` columns.
   *
   * @return string Alias for the primary table.
   */
  protected function getPrimaryTableAlias() {
    return null;
  }

epriestley's avatar
epriestley committed
416
  public function newResultObject() {
417 418 419
    return null;
  }

420

421 422 423
/* -(  Building Query Clauses  )--------------------------------------------- */


424 425 426 427 428
  /**
   * @task clauses
   */
  protected function buildSelectClause(AphrontDatabaseConnection $conn) {
    $parts = $this->buildSelectClauseParts($conn);
429
    return $this->formatSelectClause($conn, $parts);
430 431 432 433 434 435 436 437 438 439 440 441 442
  }


  /**
   * @task clauses
   */
  protected function buildSelectClauseParts(AphrontDatabaseConnection $conn) {
    $select = array();

    $alias = $this->getPrimaryTableAlias();
    if ($alias) {
      $select[] = qsprintf($conn, '%T.*', $alias);
    } else {
443
      $select[] = qsprintf($conn, '*');
444 445
    }

446
    $select[] = $this->buildEdgeLogicSelectClause($conn);
447
    $select[] = $this->buildFerretSelectClause($conn);
448

449 450 451 452 453 454 455 456 457
    return $select;
  }


  /**
   * @task clauses
   */
  protected function buildJoinClause(AphrontDatabaseConnection $conn) {
    $joins = $this->buildJoinClauseParts($conn);
458
    return $this->formatJoinClause($conn, $joins);
459 460 461 462 463 464 465 466
  }


  /**
   * @task clauses
   */
  protected function buildJoinClauseParts(AphrontDatabaseConnection $conn) {
    $joins = array();
467
    $joins[] = $this->buildEdgeLogicJoinClause($conn);
468
    $joins[] = $this->buildApplicationSearchJoinClause($conn);
469
    $joins[] = $this->buildNgramsJoinClause($conn);
470
    $joins[] = $this->buildFerretJoinClause($conn);
471 472 473 474
    return $joins;
  }


475 476 477 478
  /**
   * @task clauses
   */
  protected function buildWhereClause(AphrontDatabaseConnection $conn) {
479
    $where = $this->buildWhereClauseParts($conn);
480
    return $this->formatWhereClause($conn, $where);
481 482 483 484 485 486 487 488
  }


  /**
   * @task clauses
   */
  protected function buildWhereClauseParts(AphrontDatabaseConnection $conn) {
    $where = array();
489
    $where[] = $this->buildPagingWhereClause($conn);
490
    $where[] = $this->buildEdgeLogicWhereClause($conn);
491
    $where[] = $this->buildSpacesWhereClause($conn);
492
    $where[] = $this->buildNgramsWhereClause($conn);
493
    $where[] = $this->buildFerretWhereClause($conn);
494
    $where[] = $this->buildApplicationSearchWhereClause($conn);
495 496 497 498 499 500 501 502 503
    return $where;
  }


  /**
   * @task clauses
   */
  protected function buildHavingClause(AphrontDatabaseConnection $conn) {
    $having = $this->buildHavingClauseParts($conn);
504
    $having[] = $this->buildPagingHavingClause($conn);
505
    return $this->formatHavingClause($conn, $having);
506 507 508 509 510 511 512 513
  }


  /**
   * @task clauses
   */
  protected function buildHavingClauseParts(AphrontDatabaseConnection $conn) {
    $having = array();
514
    $having[] = $this->buildEdgeLogicHavingClause($conn);
515
    return $having;
516 517 518
  }


519 520 521 522 523
  /**
   * @task clauses
   */
  protected function buildGroupClause(AphrontDatabaseConnection $conn) {
    if (!$this->shouldGroupQueryResultRows()) {
524
      return qsprintf($conn, '');
525 526 527 528 529
    }

    return qsprintf(
      $conn,
      'GROUP BY %Q',
530
      $this->getApplicationSearchObjectPHIDColumn($conn));
531 532 533 534 535 536 537 538 539 540 541 542 543 544 545
  }


  /**
   * @task clauses
   */
  protected function shouldGroupQueryResultRows() {
    if ($this->shouldGroupEdgeLogicResultRows()) {
      return true;
    }

    if ($this->getApplicationSearchMayJoinMultipleRows()) {
      return true;
    }

546 547 548 549
    if ($this->shouldGroupNgramResultRows()) {
      return true;
    }

550 551 552 553
    if ($this->shouldGroupFerretResultRows()) {
      return true;
    }

554 555 556 557 558
    return false;
  }



559 560 561
/* -(  Paging  )------------------------------------------------------------- */


562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600
  private function buildPagingWhereClause(AphrontDatabaseConnection $conn) {
    if ($this->shouldPageWithHavingClause()) {
      return null;
    }

    return $this->buildPagingClause($conn);
  }

  private function buildPagingHavingClause(AphrontDatabaseConnection $conn) {
    if (!$this->shouldPageWithHavingClause()) {
      return null;
    }

    return $this->buildPagingClause($conn);
  }

  private function shouldPageWithHavingClause() {
    // If any of the paging conditions reference dynamic columns, we need to
    // put the paging conditions in a "HAVING" clause instead of a "WHERE"
    // clause.

    // For example, this happens when paging on the Ferret "rank" column,
    // since the "rank" value is computed dynamically in the SELECT statement.

    $orderable = $this->getOrderableColumns();
    $vector = $this->getOrderVector();

    foreach ($vector as $order) {
      $key = $order->getOrderKey();
      $column = $orderable[$key];

      if (!empty($column['having'])) {
        return true;
      }
    }

    return false;
  }

601 602 603
  /**
   * @task paging
   */
604 605
  protected function buildPagingClause(AphrontDatabaseConnection $conn) {
    $orderable = $this->getOrderableColumns();
606
    $vector = $this->getQueryableOrderVector();
607

608 609 610 611 612 613 614 615 616 617 618 619 620 621 622
    // If we don't have a cursor object yet, it means we're trying to load
    // the first result page. We may need to build a cursor object from the
    // external string, or we may not need a paging clause yet.
    $cursor_object = $this->getInternalCursorObject();
    if (!$cursor_object) {
      $external_cursor = $this->getExternalCursorString();
      if ($external_cursor !== null) {
        $cursor_object = $this->getInternalCursorFromExternalCursor(
          $external_cursor);
      }
    }

    // If we still don't have a cursor object, this is the first result page
    // and we aren't paging it. We don't need to build a paging clause.
    if (!$cursor_object) {
623
      return qsprintf($conn, '');
624 625
    }

626 627
    $reversed = $this->getIsQueryOrderReversed();

628 629 630 631
    $keys = array();
    foreach ($vector as $order) {
      $keys[] = $order->getOrderKey();
    }
632
    $keys = array_fuse($keys);
633

634 635 636
    $value_map = $this->getPagingMapFromCursorObject(
      $cursor_object,
      $keys);
637 638 639 640 641 642 643 644

    $columns = array();
    foreach ($vector as $order) {
      $key = $order->getOrderKey();

      $column = $orderable[$key];
      $column['value'] = $value_map[$key];

645 646 647 648 649 650
      // If the vector component is reversed, we need to reverse whatever the
      // order of the column is.
      if ($order->getIsReversed()) {
        $column['reverse'] = !idx($column, 'reverse', false);
      }

651 652 653 654 655 656 657 658 659 660 661
      $columns[] = $column;
    }

    return $this->buildPagingClauseFromMultipleColumns(
      $conn,
      $columns,
      array(
        'reversed' => $reversed,
      ));
  }

662

663 664 665 666 667 668 669 670 671 672 673 674 675
  /**
   * Simplifies the task of constructing a paging clause across multiple
   * columns. In the general case, this looks like:
   *
   *   A > a OR (A = a AND B > b) OR (A = a AND B = b AND C > c)
   *
   * To build a clause, specify the name, type, and value of each column
   * to include:
   *
   *   $this->buildPagingClauseFromMultipleColumns(
   *     $conn_r,
   *     array(
   *       array(
676 677
   *         'table' => 't',
   *         'column' => 'title',
678 679 680 681 682
   *         'type' => 'string',
   *         'value' => $cursor->getTitle(),
   *         'reverse' => true,
   *       ),
   *       array(
683 684
   *         'table' => 't',
   *         'column' => 'id',
685 686 687 688 689 690 691 692 693 694 695 696
   *         'type' => 'int',
   *         'value' => $cursor->getID(),
   *       ),
   *     ),
   *     array(
   *       'reversed' => $is_reversed,
   *     ));
   *
   * This method will then return a composable clause for inclusion in WHERE.
   *
   * @param AphrontDatabaseConnection Connection query will execute on.
   * @param list<map> Column description dictionaries.
Dmitri Iouchtchenko's avatar
Dmitri Iouchtchenko committed
697
   * @param map Additional construction options.
698
   * @return string Query clause.
699
   * @task paging
700 701 702 703 704 705 706 707 708 709
   */
  final protected function buildPagingClauseFromMultipleColumns(
    AphrontDatabaseConnection $conn,
    array $columns,
    array $options) {

    foreach ($columns as $column) {
      PhutilTypeSpec::checkMap(
        $column,
        array(
710
          'table' => 'optional string|null',
711
          'column' => 'string',
712 713 714
          'value' => 'wild',
          'type' => 'string',
          'reverse' => 'optional bool',
715
          'unique' => 'optional bool',
716
          'null' => 'optional string|null',
717 718
          'requires-ferret' => 'optional bool',
          'having' => 'optional bool',
719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734
        ));
    }

    PhutilTypeSpec::checkMap(
      $options,
      array(
        'reversed' => 'optional bool',
      ));

    $is_query_reversed = idx($options, 'reversed', false);

    $clauses = array();
    $accumulated = array();
    $last_key = last_key($columns);
    foreach ($columns as $key => $column) {
      $type = $column['type'];
735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764

      $null = idx($column, 'null');
      if ($column['value'] === null) {
        if ($null) {
          $value = null;
        } else {
          throw new Exception(
            pht(
              'Column "%s" has null value, but does not specify a null '.
              'behavior.',
              $key));
        }
      } else {
        switch ($type) {
          case 'int':
            $value = qsprintf($conn, '%d', $column['value']);
            break;
          case 'float':
            $value = qsprintf($conn, '%f', $column['value']);
            break;
          case 'string':
            $value = qsprintf($conn, '%s', $column['value']);
            break;
          default:
            throw new Exception(
              pht(
                'Column "%s" has unknown column type "%s".',
                $column['column'],
                $type));
        }
765 766 767 768 769 770
      }

      $is_column_reversed = idx($column, 'reverse', false);
      $reverse = ($is_query_reversed xor $is_column_reversed);

      $clause = $accumulated;
771 772 773 774 775 776 777 778 779

      $table_name = idx($column, 'table');
      $column_name = $column['column'];
      if ($table_name !== null) {
        $field = qsprintf($conn, '%T.%T', $table_name, $column_name);
      } else {
        $field = qsprintf($conn, '%T', $column_name);
      }

780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808
      $parts = array();
      if ($null) {
        $can_page_if_null = ($null === 'head');
        $can_page_if_nonnull = ($null === 'tail');

        if ($reverse) {
          $can_page_if_null = !$can_page_if_null;
          $can_page_if_nonnull = !$can_page_if_nonnull;
        }

        $subclause = null;
        if ($can_page_if_null && $value === null) {
          $parts[] = qsprintf(
            $conn,
            '(%Q IS NOT NULL)',
            $field);
        } else if ($can_page_if_nonnull && $value !== null) {
          $parts[] = qsprintf(
            $conn,
            '(%Q IS NULL)',
            $field);
        }
      }

      if ($value !== null) {
        $parts[] = qsprintf(
          $conn,
          '%Q %Q %Q',
          $field,
809
          $reverse ? qsprintf($conn, '>') : qsprintf($conn, '<'),
810 811 812 813
          $value);
      }

      if ($parts) {
814
        $clause[] = qsprintf($conn, '%LO', $parts);
815 816
      }

817
      if ($clause) {
818
        $clauses[] = qsprintf($conn, '%LA', $clause);
819 820 821 822 823 824 825 826 827 828 829 830 831 832
      }

      if ($value === null) {
        $accumulated[] = qsprintf(
          $conn,
          '%Q IS NULL',
          $field);
      } else {
        $accumulated[] = qsprintf(
          $conn,
          '%Q = %Q',
          $field,
          $value);
      }
833 834
    }

835 836 837 838 839
    if ($clauses) {
      return qsprintf($conn, '%LO', $clauses);
    }

    return qsprintf($conn, '');
840 841
  }

epriestley's avatar
epriestley committed
842 843 844 845 846

/* -(  Result Ordering  )---------------------------------------------------- */


  /**
847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862
   * Select a result ordering.
   *
   * This is a high-level method which selects an ordering from a predefined
   * list of builtin orders, as provided by @{method:getBuiltinOrders}. These
   * options are user-facing and not exhaustive, but are generally convenient
   * and meaningful.
   *
   * You can also use @{method:setOrderVector} to specify a low-level ordering
   * across individual orderable columns. This offers greater control but is
   * also more involved.
   *
   * @param string Key of a builtin order supported by this query.
   * @return this
   * @task order
   */
  public function setOrder($order) {
863
    $aliases = $this->getBuiltinOrderAliasMap();
864

865
    if (empty($aliases[$order])) {
866 867 868 869 870 871
      throw new Exception(
        pht(
          'Query "%s" does not support a builtin order "%s". Supported orders '.
          'are: %s.',
          get_class($this),
          $order,
872
          implode(', ', array_keys($aliases))));
873 874
    }

875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896
    $this->builtinOrder = $aliases[$order];
    $this->orderVector = null;

    return $this;
  }


  /**
   * Set a grouping order to apply before primary result ordering.
   *
   * This allows you to preface the query order vector with additional orders,
   * so you can effect "group by" queries while still respecting "order by".
   *
   * This is a high-level method which works alongside @{method:setOrder}. For
   * lower-level control over order vectors, use @{method:setOrderVector}.
   *
   * @param PhabricatorQueryOrderVector|list<string> List of order keys.
   * @return this
   * @task order
   */
  public function setGroupVector($vector) {
    $this->groupVector = $vector;
897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948
    $this->orderVector = null;

    return $this;
  }


  /**
   * Get builtin orders for this class.
   *
   * In application UIs, we want to be able to present users with a small
   * selection of meaningful order options (like "Order by Title") rather than
   * an exhaustive set of column ordering options.
   *
   * Meaningful user-facing orders are often really orders across multiple
   * columns: for example, a "title" ordering is usually implemented as a
   * "title, id" ordering under the hood.
   *
   * Builtin orders provide a mapping from convenient, understandable
   * user-facing orders to implementations.
   *
   * A builtin order should provide these keys:
   *
   *   - `vector` (`list<string>`): The actual order vector to use.
   *   - `name` (`string`): Human-readable order name.
   *
   * @return map<string, wild> Map from builtin order keys to specification.
   * @task order
   */
  public function getBuiltinOrders() {
    $orders = array(
      'newest' => array(
        'vector' => array('id'),
        'name' => pht('Creation (Newest First)'),
        'aliases' => array('created'),
      ),
      'oldest' => array(
        'vector' => array('-id'),
        'name' => pht('Creation (Oldest First)'),
      ),
    );

    $object = $this->newResultObject();
    if ($object instanceof PhabricatorCustomFieldInterface) {
      $list = PhabricatorCustomField::getObjectFields(
        $object,
        PhabricatorCustomField::ROLE_APPLICATIONSEARCH);
      foreach ($list->getFields() as $field) {
        $index = $field->buildOrderIndex();
        if (!$index) {
          continue;
        }

949 950
        $legacy_key = 'custom:'.$field->getFieldKey();
        $modern_key = $field->getModernFieldKey();
951

952 953
        $orders[$modern_key] = array(
          'vector' => array($modern_key, 'id'),
954
          'name' => $field->getFieldName(),
955
          'aliases' => array($legacy_key),
956
        );
957 958 959 960 961

        $orders['-'.$modern_key] = array(
          'vector' => array('-'.$modern_key, '-id'),
          'name' => pht('%s (Reversed)', $field->getFieldName()),
        );
962 963 964
      }
    }

965 966
    if ($this->supportsFerretEngine()) {
      $orders['relevance'] = array(
967
        'vector' => array('rank', 'fulltext-modified', 'id'),
epriestley's avatar
epriestley committed
968
        'name' => pht('Relevance'),
969 970 971
      );
    }

972 973 974
    return $orders;
  }

975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003
  public function getBuiltinOrderAliasMap() {
    $orders = $this->getBuiltinOrders();

    $map = array();
    foreach ($orders as $key => $order) {
      $keys = array();
      $keys[] = $key;
      foreach (idx($order, 'aliases', array()) as $alias) {
        $keys[] = $alias;
      }

      foreach ($keys as $alias) {
        if (isset($map[$alias])) {
          throw new Exception(
            pht(
              'Two builtin orders ("%s" and "%s") define the same key or '.
              'alias ("%s"). Each order alias and key must be unique and '.
              'identify a single order.',
              $key,
              $map[$alias],
              $alias));
        }
        $map[$alias] = $key;
      }
    }

    return $map;
  }

1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016

  /**
   * Set a low-level column ordering.
   *
   * This is a low-level method which offers granular control over column
   * ordering. In most cases, applications can more easily use
   * @{method:setOrder} to choose a high-level builtin order.
   *
   * To set an order vector, specify a list of order keys as provided by
   * @{method:getOrderableColumns}.
   *
   * @param PhabricatorQueryOrderVector|list<string> List of order keys.
   * @return this
epriestley's avatar
epriestley committed
1017 1018 1019 1020 1021 1022
   * @task order
   */
  public function setOrderVector($vector) {
    $vector = PhabricatorQueryOrderVector::newFromVector($vector);

    $orderable = $this->getOrderableColumns();
1023 1024 1025

    // Make sure that all the components identify valid columns.
    $unique = array();
epriestley's avatar
epriestley committed
1026
    foreach ($vector as $order) {
1027
      $key = $order->getOrderKey();
epriestley's avatar
epriestley committed
1028 1029 1030 1031 1032 1033 1034
      if (empty($orderable[$key])) {
        $valid = implode(', ', array_keys($orderable));
        throw new Exception(
          pht(
            'This query ("%s") does not support sorting by order key "%s". '.
            'Supported orders are: %s.',
            get_class($this),
1035
            $key,
epriestley's avatar
epriestley committed
1036 1037
            $valid));
      }
1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066

      $unique[$key] = idx($orderable[$key], 'unique', false);
    }

    // Make sure that the last column is unique so that this is a strong
    // ordering which can be used for paging.
    $last = last($unique);
    if ($last !== true) {
      throw new Exception(
        pht(
          'Order vector "%s" is invalid: the last column in an order must '.
          'be a column with unique values, but "%s" is not unique.',
          $vector->getAsString(),
          last_key($unique)));
    }

    // Make sure that other columns are not unique; an ordering like "id, name"
    // does not make sense because only "id" can ever have an effect.
    array_pop($unique);
    foreach ($unique as $key => $is_unique) {
      if ($is_unique) {
        throw new Exception(
          pht(
            'Order vector "%s" is invalid: only the last column in an order '.
            'may be unique, but "%s" is a unique column and not the last '.
            'column in the order.',
            $vector->getAsString(),
            $key));
      }
epriestley's avatar
epriestley committed
1067 1068 1069 1070 1071 1072 1073 1074
    }

    $this->orderVector = $vector;
    return $this;
  }


  /**
1075 1076 1077
   * Get the effective order vector.
   *
   * @return PhabricatorQueryOrderVector Effective vector.
epriestley's avatar
epriestley committed
1078 1079
   * @task order
   */
1080
  protected function getOrderVector() {
epriestley's avatar
epriestley committed
1081
    if (!$this->orderVector) {
1082 1083 1084 1085 1086 1087
      if ($this->builtinOrder !== null) {
        $builtin_order = idx($this->getBuiltinOrders(), $this->builtinOrder);
        $vector = $builtin_order['vector'];
      } else {
        $vector = $this->getDefaultOrderVector();
      }
1088 1089 1090 1091 1092 1093 1094

      if ($this->groupVector) {
        $group = PhabricatorQueryOrderVector::newFromVector($this->groupVector);
        $group->appendVector($vector);
        $vector = $group;
      }

epriestley's avatar
epriestley committed
1095
      $vector = PhabricatorQueryOrderVector::newFromVector($vector);
1096 1097 1098 1099

      // We call setOrderVector() here to apply checks to the default vector.
      // This catches any errors in the implementation.
      $this->setOrderVector($vector);
epriestley's avatar
epriestley committed
1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117
    }

    return $this->orderVector;
  }


  /**
   * @task order
   */
  protected function getDefaultOrderVector() {
    return array('id');
  }


  /**
   * @task order
   */
  public function getOrderableColumns() {
1118 1119 1120 1121 1122 1123 1124 1125 1126
    $cache = PhabricatorCaches::getRequestCache();
    $class = get_class($this);
    $cache_key = 'query.orderablecolumns.'.$class;

    $columns = $cache->getKey($cache_key);
    if ($columns !== null) {
      return $columns;
    }

1127
    $columns = array(
epriestley's avatar
epriestley committed
1128
      'id' => array(
1129
        'table' => $this->getPrimaryTableAlias(),
epriestley's avatar
epriestley committed
1130 1131
        'column' => 'id',
        'reverse' => false,
1132 1133
        'type' => 'int',
        'unique' => true,
epriestley's avatar
epriestley committed
1134 1135
      ),
    );
1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149

    $object = $this->newResultObject();
    if ($object instanceof PhabricatorCustomFieldInterface) {
      $list = PhabricatorCustomField::getObjectFields(
        $object,
        PhabricatorCustomField::ROLE_APPLICATIONSEARCH);
      foreach ($list->getFields() as $field) {
        $index = $field->buildOrderIndex();
        if (!$index) {
          continue;
        }

        $digest = $field->getFieldIndex();

1150 1151 1152
        $key = $field->getModernFieldKey();

        $columns[$key] = array(
1153 1154 1155 1156
          'table' => 'appsearch_order_'.$digest,
          'column' => 'indexValue',
          'type' => $index->getIndexValueType(),
          'null' => 'tail',
epriestley's avatar
epriestley committed
1157 1158 1159
          'customfield' => true,
          'customfield.index.table' => $index->getTableName(),
          'customfield.index.key' => $digest,
1160 1161 1162 1163
        );
      }
    }

1164 1165 1166
    if ($this->supportsFerretEngine()) {
      $columns['rank'] = array(
        'table' => null,
1167
        'column' => self::FULLTEXT_RANK,
1168
        'type' => 'int',
1169
        'requires-ferret' => true,
1170
        'having' => true,
1171
      );
1172
      $columns['fulltext-created'] = array(
1173 1174
        'table' => null,
        'column' => self::FULLTEXT_CREATED,
1175
        'type' => 'int',
1176
        'requires-ferret' => true,
1177 1178
      );