Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===-- Automaton.h - Support for driving TableGen-produced DFAs ----------===//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

//

// This file implements class that drive and introspect deterministic finite-

// state automata (DFAs) as generated by TableGen's -gen-automata backend.

//

// For a description of how to define an automaton, see

// include/llvm/TableGen/Automaton.td.

//

// One important detail is that these deterministic automata are created from

// (potentially) nondeterministic definitions. Therefore a unique sequence of

// input symbols will produce one path through the DFA but multiple paths

// through the original NFA. An automaton by default only returns "accepted" or

// "not accepted", but frequently we want to analyze what NFA path was taken.

// Finding a path through the NFA states that results in a DFA state can help

// answer *what* the solution to a problem was, not just that there exists a

// solution.

//

//===----------------------------------------------------------------------===//

#ifndef LLVM_SUPPORT_AUTOMATON_H

#define LLVM_SUPPORT_AUTOMATON_H

#include "llvm/ADT/ArrayRef.h"

#include "llvm/ADT/DenseMap.h"

#include "llvm/ADT/SmallVector.h"

#include "llvm/Support/Allocator.h"

#include <deque>

#include <map>

#include <memory>

#include <unordered_map>

#include <vector>

namespace llvm {

using NfaPath = SmallVector<uint64_t, 4>;

/// Forward define the pair type used by the automata transition info tables.

///

/// Experimental results with large tables have shown a significant (multiple

/// orders of magnitude) parsing speedup by using a custom struct here with a

/// trivial constructor rather than std::pair<uint64_t, uint64_t>.

struct NfaStatePair {

  uint64_t FromDfaState, ToDfaState;

  bool operator<(const NfaStatePair &Other) const {

    return std::make_tuple(FromDfaState, ToDfaState) <

           std::make_tuple(Other.FromDfaState, Other.ToDfaState);

  }

};

namespace internal {

/// The internal class that maintains all possible paths through an NFA based

/// on a path through the DFA.

class NfaTranscriber {

private:

  /// Cached transition table. This is a table of NfaStatePairs that contains

  /// zero-terminated sequences pointed to by DFA transitions.

  ArrayRef<NfaStatePair> TransitionInfo;

  /// A simple linked-list of traversed states that can have a shared tail. The

  /// traversed path is stored in reverse order with the latest state as the

  /// head.

  struct PathSegment {

    uint64_t State;

    PathSegment *Tail;

  };

  /// We allocate segment objects frequently. Allocate them upfront and dispose

  /// at the end of a traversal rather than hammering the system allocator.

  SpecificBumpPtrAllocator<PathSegment> Allocator;

  /// Heads of each tracked path. These are not ordered.

  std::deque<PathSegment *> Heads;

  /// The returned paths. This is populated during getPaths.

  SmallVector<NfaPath, 4> Paths;

  /// Create a new segment and return it.

  PathSegment *makePathSegment(uint64_t State, PathSegment *Tail) {

    PathSegment *P = Allocator.Allocate();

    *P = {State, Tail};

    return P;

  }

  /// Pairs defines a sequence of possible NFA transitions for a single DFA

  /// transition.

  void transition(ArrayRef<NfaStatePair> Pairs) {

    // Iterate over all existing heads. We will mutate the Heads deque during

    // iteration.

    unsigned NumHeads = Heads.size();

    for (unsigned I = 0; I < NumHeads; ++I) {

      PathSegment *Head = Heads[I];

      // The sequence of pairs is sorted. Select the set of pairs that

      // transition from the current head state.

      auto PI = lower_bound(Pairs, NfaStatePair{Head->State, 0ULL});

      auto PE = upper_bound(Pairs, NfaStatePair{Head->State, INT64_MAX});

      // For every transition from the current head state, add a new path

      // segment.

      for (; PI != PE; ++PI)

        if (PI->FromDfaState == Head->State)

          Heads.push_back(makePathSegment(PI->ToDfaState, Head));

    }

    // Now we've iterated over all the initial heads and added new ones,

    // dispose of the original heads.

    Heads.erase(Heads.begin(), std::next(Heads.begin(), NumHeads));

  }

public:

  NfaTranscriber(ArrayRef<NfaStatePair> TransitionInfo)

      : TransitionInfo(TransitionInfo) {

    reset();

  }

  ArrayRef<NfaStatePair> getTransitionInfo() const {

    return TransitionInfo;

  }

  void reset() {

    Paths.clear();

    Heads.clear();

    Allocator.DestroyAll();

    // The initial NFA state is 0.

    Heads.push_back(makePathSegment(0ULL, nullptr));

  }

  void transition(unsigned TransitionInfoIdx) {

    unsigned EndIdx = TransitionInfoIdx;

    while (TransitionInfo[EndIdx].ToDfaState != 0)

      ++EndIdx;

    ArrayRef<NfaStatePair> Pairs(&TransitionInfo[TransitionInfoIdx],

                                 EndIdx - TransitionInfoIdx);

    transition(Pairs);

  }

  ArrayRef<NfaPath> getPaths() {

    Paths.clear();

    for (auto *Head : Heads) {

      NfaPath P;

      while (Head->State != 0) {

        P.push_back(Head->State);

        Head = Head->Tail;

      }

      std::reverse(P.begin(), P.end());

      Paths.push_back(std::move(P));

    }

    return Paths;

  }

};

} // namespace internal

/// A deterministic finite-state automaton. The automaton is defined in

/// TableGen; this object drives an automaton defined by tblgen-emitted tables.

///

/// An automaton accepts a sequence of input tokens ("actions"). This class is

/// templated on the type of these actions.

template <typename ActionT> class Automaton {

  /// Map from {State, Action} to {NewState, TransitionInfoIdx}.

  /// TransitionInfoIdx is used by the DfaTranscriber to analyze the transition.

  /// FIXME: This uses a std::map because ActionT can be a pair type including

  /// an enum. In particular DenseMapInfo<ActionT> must be defined to use

  /// DenseMap here.

  /// This is a shared_ptr to allow very quick copy-construction of Automata; this

  /// state is immutable after construction so this is safe.

  using MapTy = std::map<std::pair<uint64_t, ActionT>, std::pair<uint64_t, unsigned>>;

  std::shared_ptr<MapTy> M;

  /// An optional transcription object. This uses much more state than simply

  /// traversing the DFA for acceptance, so is heap allocated.

  std::shared_ptr<internal::NfaTranscriber> Transcriber;

  /// The initial DFA state is 1.

  uint64_t State = 1;

  /// True if we should transcribe and false if not (even if Transcriber is defined).

  bool Transcribe;

public:

  /// Create an automaton.

  /// \param Transitions The Transitions table as created by TableGen. Note that

  ///                    because the action type differs per automaton, the

  ///                    table type is templated as ArrayRef<InfoT>.

  /// \param TranscriptionTable The TransitionInfo table as created by TableGen.

  ///

  /// Providing the TranscriptionTable argument as non-empty will enable the

  /// use of transcription, which analyzes the possible paths in the original

  /// NFA taken by the DFA. NOTE: This is substantially more work than simply

  /// driving the DFA, so unless you require the getPaths() method leave this

  /// empty.

  template <typename InfoT>

  Automaton(ArrayRef<InfoT> Transitions,

            ArrayRef<NfaStatePair> TranscriptionTable = {}) {

    if (!TranscriptionTable.empty())

      Transcriber =

          std::make_shared<internal::NfaTranscriber>(TranscriptionTable);

    Transcribe = Transcriber != nullptr;

    M = std::make_shared<MapTy>();

    for (const auto &I : Transitions)

      // Greedily read and cache the transition table.

      M->emplace(std::make_pair(I.FromDfaState, I.Action),

                 std::make_pair(I.ToDfaState, I.InfoIdx));

  }

  Automaton(const Automaton &Other)

      : M(Other.M), State(Other.State), Transcribe(Other.Transcribe) {

    // Transcriber is not thread-safe, so create a new instance on copy.

    if (Other.Transcriber)

      Transcriber = std::make_shared<internal::NfaTranscriber>(

          Other.Transcriber->getTransitionInfo());

  }

  /// Reset the automaton to its initial state.

  void reset() {

    State = 1;

    if (Transcriber)

      Transcriber->reset();

  }

  /// Enable or disable transcription. Transcription is only available if

  /// TranscriptionTable was provided to the constructor.

  void enableTranscription(bool Enable = true) {

    assert(Transcriber &&

           "Transcription is only available if TranscriptionTable was provided "

           "to the Automaton constructor");

    Transcribe = Enable;

  }

  /// Transition the automaton based on input symbol A. Return true if the

  /// automaton transitioned to a valid state, false if the automaton

  /// transitioned to an invalid state.

  ///

  /// If this function returns false, all methods are undefined until reset() is

  /// called.

  bool add(const ActionT &A) {

    auto I = M->find({State, A});

    if (I == M->end())

      return false;

    if (Transcriber && Transcribe)

      Transcriber->transition(I->second.second);

    State = I->second.first;

    return true;

  }

  /// Return true if the automaton can be transitioned based on input symbol A.

  bool canAdd(const ActionT &A) {

    auto I = M->find({State, A});

    return I != M->end();

  }

  /// Obtain a set of possible paths through the input nondeterministic

  /// automaton that could be obtained from the sequence of input actions

  /// presented to this deterministic automaton.

  ArrayRef<NfaPath> getNfaPaths() {

    assert(Transcriber && Transcribe &&

           "Can only obtain NFA paths if transcribing!");

    return Transcriber->getPaths();

  }

};

} // namespace llvm

#endif // LLVM_SUPPORT_AUTOMATON_H