view release on metacpan or  search on metacpan

ConstructDFA.xs  view on Meta::CPAN

  }
  void pop_back() {
    auto back_element = back();
    included[back_element] = false;
    elements.pop_back();
  }
  void clear() {
    included.clear();
    elements.clear();
  }
};

void
add_all_reachable_and_self(
  VectorBasedSet<State>& todo,
  VectorBasedSet<State>& s,
  map<State, bool>& nullable,
  map<State, vector<State>>& successors) {

  for (auto i = s.elements.begin(); i != s.elements.end(); ++i) {
    if (!nullable[*i])
      continue;

    auto x = successors[*i];
    
    for (auto k = x.begin(); k != x.end(); ++k)
      todo.insert(*k);
  }

  while (!todo.empty()) {
    State current = todo.back();
    todo.pop_back();

    if (s.contains(current)) {
      continue;
    }

    s.insert(current);

    if (nullable[current]) {
      auto x = successors[current];
      
      for (auto i = x.begin(); i != x.end(); ++i)
        todo.insert(*i);
    }
  }
}

bool does_accept(SV* accept_sv, vector<State> s) {
  dSP;

  ENTER;
  SAVETMPS;

  PUSHMARK(SP);
  
  for (auto i = s.begin(); i != s.end(); ++i) {
    mXPUSHs(newSVuv(*i));
  }

  PUTBACK;

  I32 count = call_sv(accept_sv, G_SCALAR);

  SPAGAIN;

  bool result = false;

  if (count == 1) {
    result = (bool)POPi;
  } else {
    warn("bad accept");
  }

  PUTBACK;
  FREETMPS;
  LEAVE;

  return result;
}

class StatesBimap {
public:
  std::map<vector<State>, StatesId> s2id;
  std::vector<vector<State>> id2s;

  StatesBimap() {
    states_to_id(States());
  };
  
  StatesId states_to_id(const States& s) {
    vector<State> v;
    
    std::copy(s.begin(), s.end(),
      std::back_inserter(v));
    
    return states_to_id(v);
  }

  StatesId states_to_id(const vector<State>& s) {
    auto v = s;
    std::sort(v.begin(), v.end());
    
    if (s2id.find(v) == s2id.end()) {
      s2id[v] = id2s.size();
      id2s.push_back(v);
    }
    return s2id[v];
  }
  
  const vector<State>& id_to_states(StatesId id) {
    if (id >= id2s.size()) {
      warn("Programmer error looking up %u", id);
    }
    return id2s[id];
  }
};

map<size_t, HV*>
build_dfa(SV* accept_sv, AV* args) {

  typedef map<pair<StatesId, Label>, StatesId> Automaton;
  StatesBimap               m;
  VectorBasedSet<State>     sub_todo;

  // Input from Perl
  map<State, vector<State>> successors;
  map<State, bool>          nullable;
  map<State, Label>         label;
  map<size_t, States>       start_states;
  
  I32 args_len = av_len(args);

  for (int ix = 0; ix <= args_len; ++ix) {
    SV** current_svp = av_fetch(args, ix, 0);

ConstructDFA.xs  view on Meta::CPAN

    auto he1 = hv_store(state_hv, "Accepts", 7, newSVuv(accepting[s->second]), 0);
    auto he2 = hv_store(state_hv, "Combines", 8, combines_rv, 0);
    auto he3 = hv_store(state_hv, "NextOver", 8, next_over_rv, 0);

    vector<State> x = m.id_to_states(s->second);

    for (auto k = x.begin(); k != x.end(); ++k) {
      av_push(combines_av, newSVuv(*k));
    }

    dfa[s->first] = state_hv;

    id_to_hvs.insert(make_pair(s->second, state_hv));
  }

  for (auto s = automaton.begin(); s != automaton.end(); ++s) {
    StatesId srcId  = s->first.first;
    Label label = s->first.second;
    StatesId dstId  = s->second;

    if (dfa.find(state_map[srcId]) == dfa.end()) {
      croak("...");
    }
    
    for (auto p = id_to_hvs.find(srcId); p != id_to_hvs.end(); ++p) {
      if (p->first != srcId)
        break;
        
      SV** next_over_svp = hv_fetch(p->second, "NextOver", 8, 0);
      
      if (!next_over_svp)
        croak("...");
        
      SV* label_sv = newSVuv(label);  
        
      HE* he = hv_store_ent((HV*)SvRV(*next_over_svp),
        label_sv, newSVuv(state_map[dstId]), 0);

      if (he == NULL) {
        warn("hv_store_ent failed");
        SvREFCNT_dec(label_sv);
      }
    }
  }
  
  return dfa;
}

MODULE = Algorithm::ConstructDFA::XS  PACKAGE = Algorithm::ConstructDFA::XS

void
_internal_construct_dfa_xs(accepts_sv, args_sv)
    SV* accepts_sv
    SV* args_sv
  PREINIT:
    AV* args;
  PPCODE:
    args = (AV*)SvRV(args_sv);

    PUTBACK;
    auto dfa = build_dfa(accepts_sv, args);
    SPAGAIN;

    for (auto i = dfa.begin(); i != dfa.end(); ++i) {
      mXPUSHs(newSVuv(i->first));
      mXPUSHs(newRV_noinc((SV*)(i->second)));
    }