author Ted Mielczarek <>
Fri, 06 Jan 2017 05:57:10 -0500
changeset 328603 dedf4f49b3756b09986e78dc5519a291b81f133f
parent 325807 29b6c0a80512eaf0359c90cc398bcc1722533fe6
child 352206 a6c0e4789330b9a37956bcb123449db35e27e6f0
permissions -rw-r--r--
bug 1329320 - replace makecab with rust-makecab in symbolstore. r=gps It turns out that running makecab to compress PDB files takes a significant amount of time in the buildsymbols step. I wrote an implementation of makecab in Rust that implements only the subset of features we use and it's significantly faster: This patch adds a makecab check to moz.configure, adds a release build of the makecab binary to the Windows tooltool manifests, points the build at it from, and changes to use MAKECAB from substs instead of calling `makecab.exe` directly. MozReview-Commit-ID: 76FHLIZFCXS

/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*-
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at */


#include "mozilla/gfx/Polygon.h"
#include "mozilla/Move.h"
#include "mozilla/UniquePtr.h"
#include "nsTArray.h"

#include <deque>

namespace mozilla {
namespace layers {

class Layer;

// Represents a layer that might have a non-rectangular geometry.
struct LayerPolygon {
  explicit LayerPolygon(Layer *aLayer)
    : layer(aLayer) {}

  LayerPolygon(Layer *aLayer,
               gfx::Polygon&& aGeometry)
    : layer(aLayer), geometry(Some(aGeometry)) {}

  LayerPolygon(Layer *aLayer,
               nsTArray<gfx::Point4D>&& aPoints,
               const gfx::Point4D& aNormal)
    : layer(aLayer), geometry(Some(gfx::Polygon(Move(aPoints), aNormal))) {}

  Layer *layer;
  Maybe<gfx::Polygon> geometry;

LayerPolygon PopFront(std::deque<LayerPolygon>& aLayers);

// Represents a node in a BSP tree. The node contains at least one layer with
// associated geometry that is used as a splitting plane, and at most two child
// nodes that represent the splitting planes that further subdivide the space.
struct BSPTreeNode {
  explicit BSPTreeNode(LayerPolygon&& layer)

  const gfx::Polygon& First() const
    return *layers[0].geometry;

  UniquePtr<BSPTreeNode> front;
  UniquePtr<BSPTreeNode> back;
  std::deque<LayerPolygon> layers;

// BSPTree class takes a list of layers as an input and uses binary space
// partitioning algorithm to create a tree structure that can be used for
// depth sorting.
// Sources for more information:
class BSPTree {
  // This constructor takes the ownership of layers in the given list.
  explicit BSPTree(std::deque<LayerPolygon>& aLayers)
    mRoot.reset(new BSPTreeNode(PopFront(aLayers)));

    BuildTree(mRoot, aLayers);

  // Returns the root node of the BSP tree.
  const UniquePtr<BSPTreeNode>& GetRoot() const
    return mRoot;

  // Builds and returns the back-to-front draw order for the created BSP tree.
  nsTArray<LayerPolygon> GetDrawOrder() const
    nsTArray<LayerPolygon> layers;
    BuildDrawOrder(mRoot, layers);
    return layers;

  UniquePtr<BSPTreeNode> mRoot;

  // BuildDrawOrder and BuildTree are called recursively. The depth of the
  // recursion depends on the amount of polygons and their intersections.
  void BuildDrawOrder(const UniquePtr<BSPTreeNode>& aNode,
                      nsTArray<LayerPolygon>& aLayers) const;
  void BuildTree(UniquePtr<BSPTreeNode>& aRoot,
                 std::deque<LayerPolygon>& aLayers);

} // namespace layers
} // namespace mozilla