xpcom/ds/Dafsa.cpp
author Chris Peterson <cpeterson@mozilla.com>
Sun, 24 Feb 2019 17:35:59 -0800
changeset 464363 5ff84e853d700af894616574f581551a88a93dc7
parent 448947 6f3709b3878117466168c40affa7bca0b60cf75b
permissions -rw-r--r--
Bug 1534878 - xpcom: Make some global functions static. r=erahm clang's -Wmissing-prototypes option identifies global functions that can be made static (because they're only called from one compilation unit) or removed (if they're never called). xpcom/base/Logging.cpp:85:13 [-Wmissing-prototypes] no previous prototype for function 'ToLogStr' xpcom/base/Logging.cpp:132:13 [-Wmissing-prototypes] no previous prototype for function 'ExpandPIDMarker' xpcom/base/LogModulePrefWatcher.cpp:37:6 [-Wmissing-prototypes] no previous prototype for function 'ResetExistingPrefs' xpcom/base/LogModulePrefWatcher.cpp:109:6 [-Wmissing-prototypes] no previous prototype for function 'LoadExistingPrefs' xpcom/base/nsCycleCollector.cpp:212:6 [-Wmissing-prototypes] no previous prototype for function 'SuspectUsingNurseryPurpleBuffer' xpcom/components/nsComponentManager.cpp:421:31 [-Wmissing-prototypes] no previous prototype for function 'begin' xpcom/components/nsComponentManager.cpp:427:31 [-Wmissing-prototypes] no previous prototype for function 'end' xpcom/ds/Dafsa.cpp:23:6 [-Wmissing-prototypes] no previous prototype for function 'GetNextOffset' xpcom/ds/Dafsa.cpp:55:6 [-Wmissing-prototypes] no previous prototype for function 'IsEOL' xpcom/ds/Dafsa.cpp:62:6 [-Wmissing-prototypes] no previous prototype for function 'IsMatch' xpcom/ds/Dafsa.cpp:70:6 [-Wmissing-prototypes] no previous prototype for function 'IsEndCharMatch' xpcom/ds/Dafsa.cpp:78:6 [-Wmissing-prototypes] no previous prototype for function 'GetReturnValue' xpcom/ds/Dafsa.cpp:91:5 [-Wmissing-prototypes] no previous prototype for function 'LookupString' xpcom/io/CocoaFileUtils.mm:195:13 [-Wmissing-prototypes] no previous prototype for function 'GetQuarantinePropKey' xpcom/io/CocoaFileUtils.mm:203:24 [-Wmissing-prototypes] no previous prototype for function 'CreateQuarantineDictionary' xpcom/rust/gtest/bench-collections/Bench.cpp:65:11 [-Wmissing-prototypes] no previous prototype for function 'MyRand' xpcom/rust/gtest/bench-collections/Bench.cpp:85:6 [-Wmissing-prototypes] no previous prototype for function 'Bench_Cpp_unordered_set' xpcom/rust/gtest/bench-collections/Bench.cpp:125:6 [-Wmissing-prototypes] no previous prototype for function 'Bench_Cpp_PLDHashTable' xpcom/rust/gtest/bench-collections/Bench.cpp:166:6 [-Wmissing-prototypes] no previous prototype for function 'Bench_Cpp_MozHashSet' xpcom/tests/gtest/TestAtoms.cpp:114:6 [-Wmissing-prototypes] no previous prototype for function 'isStaticAtom' xpcom/tests/gtest/TestCallTemplates.cpp:72:6 [-Wmissing-prototypes] no previous prototype for function 'JustTestingCompilation' xpcom/tests/gtest/TestCOMPtr.cpp:87:10 [-Wmissing-prototypes] no previous prototype for function 'CreateIFoo' xpcom/tests/gtest/TestCOMPtr.cpp:98:6 [-Wmissing-prototypes] no previous prototype for function 'set_a_IFoo' xpcom/tests/gtest/TestCOMPtr.cpp:105:16 [-Wmissing-prototypes] no previous prototype for function 'return_a_IFoo' xpcom/tests/gtest/TestCOMPtr.cpp:164:10 [-Wmissing-prototypes] no previous prototype for function 'CreateIBar' xpcom/tests/gtest/TestCOMPtr.cpp:175:6 [-Wmissing-prototypes] no previous prototype for function 'AnIFooPtrPtrContext' xpcom/tests/gtest/TestCOMPtr.cpp:177:6 [-Wmissing-prototypes] no previous prototype for function 'AVoidPtrPtrContext' xpcom/tests/gtest/TestCOMPtr.cpp:179:6 [-Wmissing-prototypes] no previous prototype for function 'AnISupportsPtrPtrContext' xpcom/tests/gtest/TestCOMPtr.cpp:263:6 [-Wmissing-prototypes] no previous prototype for function 'Comparison' xpcom/tests/gtest/TestCOMPtr.cpp:298:6 [-Wmissing-prototypes] no previous prototype for function 'DontAddRef' xpcom/tests/gtest/TestCRT.cpp:17:5 [-Wmissing-prototypes] no previous prototype for function 'sign' xpcom/tests/gtest/TestDeadlockDetector.cpp:62:6 [-Wmissing-prototypes] no previous prototype for function 'DisableCrashReporter' xpcom/tests/gtest/TestDeadlockDetector.cpp:74:5 [-Wmissing-prototypes] no previous prototype for function 'Sanity_Child' xpcom/tests/gtest/TestDeadlockDetector.cpp:95:5 [-Wmissing-prototypes] no previous prototype for function 'Sanity2_Child' xpcom/tests/gtest/TestDeadlockDetector.cpp:159:5 [-Wmissing-prototypes] no previous prototype for function 'Sanity4_Child' xpcom/tests/gtest/TestDeadlockDetector.cpp:182:5 [-Wmissing-prototypes] no previous prototype for function 'Sanity5_Child' xpcom/tests/gtest/TestDeadlockDetector.cpp:303:5 [-Wmissing-prototypes] no previous prototype for function 'ContentionNoDeadlock_Child' xpcom/tests/gtest/TestHashtables.cpp:88:6 [-Wmissing-prototypes] no previous prototype for function 'testTHashtable' xpcom/tests/gtest/TestHashtables.cpp:205:10 [-Wmissing-prototypes] no previous prototype for function 'CreateIFoo' xpcom/tests/gtest/TestMoveString.cpp:25:6 [-Wmissing-prototypes] no previous prototype for function 'SetAsOwned' xpcom/tests/gtest/TestMoveString.cpp:34:6 [-Wmissing-prototypes] no previous prototype for function 'ExpectTruncated' xpcom/tests/gtest/TestMoveString.cpp:40:6 [-Wmissing-prototypes] no previous prototype for function 'ExpectNew' xpcom/tests/gtest/TestMruCache.cpp:52:11 [-Wmissing-prototypes] no previous prototype for function 'MakeStringKey' xpcom/tests/gtest/TestMultiplexInputStream.cpp:106:34 [-Wmissing-prototypes] no previous prototype for function 'CreateStreamHelper' xpcom/tests/gtest/TestNonBlockingAsyncInputStream.cpp:62:10 [-Wmissing-prototypes] no previous prototype for function 'ReadSegmentsFunction' xpcom/tests/gtest/TestNsDeque.cpp:240:6 [-Wmissing-prototypes] no previous prototype for function 'CheckIfQueueEmpty' xpcom/tests/gtest/TestNsRefPtr.cpp:105:10 [-Wmissing-prototypes] no previous prototype for function 'CreateFoo' xpcom/tests/gtest/TestNsRefPtr.cpp:116:6 [-Wmissing-prototypes] no previous prototype for function 'set_a_Foo' xpcom/tests/gtest/TestNsRefPtr.cpp:123:13 [-Wmissing-prototypes] no previous prototype for function 'return_a_Foo' xpcom/tests/gtest/TestNsRefPtr.cpp:391:6 [-Wmissing-prototypes] no previous prototype for function 'AnFooPtrPtrContext' xpcom/tests/gtest/TestNsRefPtr.cpp:392:6 [-Wmissing-prototypes] no previous prototype for function 'AVoidPtrPtrContext' xpcom/tests/gtest/TestPLDHash.cpp:33:6 [-Wmissing-prototypes] no previous prototype for function 'TestCrashyOperation' xpcom/tests/gtest/TestPipes.cpp:98:10 [-Wmissing-prototypes] no previous prototype for function 'TestPipe' xpcom/tests/gtest/TestPipes.cpp:212:10 [-Wmissing-prototypes] no previous prototype for function 'TestShortWrites' xpcom/tests/gtest/TestPipes.cpp:354:6 [-Wmissing-prototypes] no previous prototype for function 'RunTests' xpcom/tests/gtest/TestPLDHash.cpp:90:6 [-Wmissing-prototypes] no previous prototype for function 'InitCapacityOk_InitialLengthTooBig' xpcom/tests/gtest/TestPLDHash.cpp:95:6 [-Wmissing-prototypes] no previous prototype for function 'InitCapacityOk_InitialEntryStoreTooBig' xpcom/tests/gtest/TestPLDHash.cpp:102:6 [-Wmissing-prototypes] no previous prototype for function 'InitCapacityOk_EntrySizeTooBig' xpcom/tests/gtest/TestSlicedInputStream.cpp:111:20 [-Wmissing-prototypes] no previous prototype for function 'CreateSeekableStreams' xpcom/tests/gtest/TestSlicedInputStream.cpp:125:20 [-Wmissing-prototypes] no previous prototype for function 'CreateNonSeekableStreams' xpcom/tests/gtest/TestStrings.cpp:471:6 [-Wmissing-prototypes] no previous prototype for function 'test_assign_helper' xpcom/tests/gtest/TestTArray.cpp:60:22 [-Wmissing-prototypes] no previous prototype for function 'DummyArray' xpcom/tests/gtest/TestTArray.cpp:72:22 [-Wmissing-prototypes] no previous prototype for function 'FakeHugeArray' xpcom/tests/gtest/TestThrottledEventQueue.cpp:96:6 [-Wmissing-prototypes] no previous prototype for function 'Enqueue' xpcom/threads/BlockingResourceBase.cpp:86:6 [-Wmissing-prototypes] no previous prototype for function 'PrintCycle' xpcom/threads/CPUUsageWatcher.cpp:41:10 [-Wmissing-prototypes] no previous prototype for function 'GetMicroseconds' xpcom/threads/CPUUsageWatcher.cpp:46:10 [-Wmissing-prototypes] no previous prototype for function 'GetMicroseconds' xpcom/threads/CPUUsageWatcher.cpp:51:40 [-Wmissing-prototypes] no previous prototype for function 'GetProcessCPUStats' xpcom/threads/CPUUsageWatcher.cpp:80:40 [-Wmissing-prototypes] no previous prototype for function 'GetGlobalCPUStats' xpcom/threads/nsTimerImpl.cpp:196:21 [-Wmissing-prototypes] no previous prototype for function 'GetTimerFiringsLog' Differential Revision: https://phabricator.services.mozilla.com/D23264

/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* 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 http://mozilla.org/MPL/2.0/. */

// Copyright (c) 2012 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "Dafsa.h"

#include "mozilla/Assertions.h"
#include "nsAString.h"

const int mozilla::Dafsa::kKeyNotFound = -1;

// Note the DAFSA implementation was lifted from eTLD code in Chromium that was
// originally lifted from Firefox.

// Read next offset from pos.
// Returns true if an offset could be read, false otherwise.
static bool GetNextOffset(const unsigned char** pos, const unsigned char* end,
                          const unsigned char** offset) {
  if (*pos == end) return false;

  // When reading an offset the byte array must always contain at least
  // three more bytes to consume. First the offset to read, then a node
  // to skip over and finally a destination node. No object can be smaller
  // than one byte.
  MOZ_ASSERT(*pos + 2 < end);
  size_t bytes_consumed;
  switch (**pos & 0x60) {
    case 0x60:  // Read three byte offset
      *offset += (((*pos)[0] & 0x1F) << 16) | ((*pos)[1] << 8) | (*pos)[2];
      bytes_consumed = 3;
      break;
    case 0x40:  // Read two byte offset
      *offset += (((*pos)[0] & 0x1F) << 8) | (*pos)[1];
      bytes_consumed = 2;
      break;
    default:
      *offset += (*pos)[0] & 0x3F;
      bytes_consumed = 1;
  }
  if ((**pos & 0x80) != 0) {
    *pos = end;
  } else {
    *pos += bytes_consumed;
  }
  return true;
}

// Check if byte at offset is last in label.
static bool IsEOL(const unsigned char* offset, const unsigned char* end) {
  MOZ_ASSERT(offset < end);
  return (*offset & 0x80) != 0;
}

// Check if byte at offset matches first character in key.
// This version matches characters not last in label.
static bool IsMatch(const unsigned char* offset, const unsigned char* end,
                    const char* key) {
  MOZ_ASSERT(offset < end);
  return *offset == *key;
}

// Check if byte at offset matches first character in key.
// This version matches characters last in label.
static bool IsEndCharMatch(const unsigned char* offset,
                           const unsigned char* end, const char* key) {
  MOZ_ASSERT(offset < end);
  return *offset == (*key | 0x80);
}

// Read return value at offset.
// Returns true if a return value could be read, false otherwise.
static bool GetReturnValue(const unsigned char* offset,
                           const unsigned char* end, int* return_value) {
  MOZ_ASSERT(offset < end);
  if ((*offset & 0xE0) == 0x80) {
    *return_value = *offset & 0x0F;
    return true;
  }
  return false;
}

// Lookup a domain key in a byte array generated by make_dafsa.py.
// The rule type is returned if key is found, otherwise kKeyNotFound is
// returned.
static int LookupString(const unsigned char* graph, size_t length,
                        const char* key, size_t key_length) {
  const unsigned char* pos = graph;
  const unsigned char* end = graph + length;
  const unsigned char* offset = pos;
  const char* key_end = key + key_length;
  while (GetNextOffset(&pos, end, &offset)) {
    //   char <char>+ end_char offsets
    //   char <char>+ return value
    //   char end_char offsets
    //   char return value
    //   end_char offsets
    //   return_value
    bool did_consume = false;
    if (key != key_end && !IsEOL(offset, end)) {
      // Leading <char> is not a match. Don't dive into this child
      if (!IsMatch(offset, end, key)) continue;
      did_consume = true;
      ++offset;
      ++key;
      // Possible matches at this point:
      // <char>+ end_char offsets
      // <char>+ return value
      // end_char offsets
      // return value
      // Remove all remaining <char> nodes possible
      while (!IsEOL(offset, end) && key != key_end) {
        if (!IsMatch(offset, end, key)) return mozilla::Dafsa::kKeyNotFound;
        ++key;
        ++offset;
      }
    }
    // Possible matches at this point:
    // end_char offsets
    // return_value
    // If one or more <char> elements were consumed, a failure
    // to match is terminal. Otherwise, try the next node.
    if (key == key_end) {
      int return_value;
      if (GetReturnValue(offset, end, &return_value)) return return_value;
      // The DAFSA guarantees that if the first char is a match, all
      // remaining char elements MUST match if the key is truly present.
      if (did_consume) return mozilla::Dafsa::kKeyNotFound;
      continue;
    }
    if (!IsEndCharMatch(offset, end, key)) {
      if (did_consume) return mozilla::Dafsa::kKeyNotFound;  // Unexpected
      continue;
    }
    ++key;
    pos = ++offset;  // Dive into child
  }
  return mozilla::Dafsa::kKeyNotFound;  // No match
}

namespace mozilla {

int Dafsa::Lookup(const nsACString& aKey) const {
  return LookupString(mData.Elements(), mData.Length(), aKey.BeginReading(),
                      aKey.Length());
}

}  // namespace mozilla