Skip to content
Snippets Groups Projects
Select Git revision
  • master default protected
  • fullUD
  • movementInAction
3 results

ActionBank.cpp

Blame
    • ActionBank.cpp 20.34 KiB 
    #include "ActionBank.hpp"
#include "Config.hpp"
#include "util.hpp"
#include "ProgramParameters.hpp"

Action::BasicAction ActionBank::moveHead(int movement)
{
  auto apply = [movement](Config & c, Action::BasicAction &)
    {c.moveHead(movement);};
  auto undo = [movement](Config & c, Action::BasicAction &)
    {c.moveHead(-movement);};
  auto appliable = [movement](Config &, Action::BasicAction &)
    {return true;};
  Action::BasicAction basicAction =
    {Action::BasicAction::Type::MoveHead, "", apply, undo, appliable};

  return basicAction;
}

Action::BasicAction ActionBank::bufferWrite(std::string tapeName, std::string value, int relativeIndex)
{
  auto apply = [tapeName, value, relativeIndex](Config & c, Action::BasicAction &)
    {
      simpleBufferWrite(c, tapeName, value, relativeIndex);
    };
  auto undo = [tapeName, relativeIndex](Config & c, Action::BasicAction &)
    {
      simpleBufferWrite(c, tapeName, "", relativeIndex);
    };
  auto appliable = [tapeName, relativeIndex](Config & c, Action::BasicAction &)
    {
      return simpleBufferWriteAppliable(c, tapeName, relativeIndex);
    };
  Action::BasicAction basicAction =
    {Action::BasicAction::Type::Write, value, apply, undo, appliable};

  return basicAction;
}

Action::BasicAction ActionBank::stackWrite(std::string tapeName, std::string value, int stackIndex)
{
  auto apply = [tapeName, value, stackIndex](Config & c, Action::BasicAction &)
    {
      int bufferIndex = c.stackGetElem(stackIndex);
      int relativeIndex = bufferIndex - c.getHead();
      simpleBufferWrite(c, tapeName, value, relativeIndex);
    };
  auto undo = [tapeName, stackIndex](Config & c, Action::BasicAction &)
    {
      int bufferIndex = c.stackGetElem(stackIndex);
      int relativeIndex = bufferIndex - c.getHead();
      simpleBufferWrite(c, tapeName, "", relativeIndex);
    };
  auto appliable = [tapeName, stackIndex](Config & c, Action::BasicAction &)
    {
      if (!c.stackHasIndex(stackIndex))
        return false;
      int bufferIndex = c.stackGetElem(stackIndex);
      int relativeIndex = bufferIndex - c.getHead();
      return simpleBufferWriteAppliable(c, tapeName, relativeIndex);
    };

  Action::BasicAction basicAction =
    {Action::BasicAction::Type::Write, value, apply, undo, appliable};

  return basicAction;
}

Action::BasicAction ActionBank::pushHead()
{
        auto apply = [](Config & c, Action::BasicAction &)
      {c.stackPush(c.getHead());};
    auto undo = [](Config & c, Action::BasicAction &)
      {c.stackPop();};
    auto appliable = [](Config & c, Action::BasicAction &)
      {return !(c.stackSize() >= ProgramParameters::maxStackSize) && (!c.endOfTapes());};
    Action::BasicAction basicAction =
      {Action::BasicAction::Type::Push, "", apply, undo, appliable};

    return basicAction;
}

Action::BasicAction ActionBank::stackPop(bool checkGov)
{
  auto apply = [](Config & c, Action::BasicAction & ba)
    {ba.data = std::to_string(c.stackTop());
     c.stackPop();};
  auto undo = [](Config & c, Action::BasicAction & ba)
    {c.stackPush(std::stoi(ba.data));};
  auto appliable = [checkGov](Config & c, Action::BasicAction &)
    {
      if (c.stackEmpty())
        return false;
      if (!checkGov)
        return true;

      return !c.getTape("GOV").getHyp(c.stackTop()-c.getHead()).empty();
    };
  Action::BasicAction basicAction =
    {Action::BasicAction::Type::Pop, "", apply, undo, appliable};

  return basicAction;
}

std::vector<Action::BasicAction> ActionBank::str2sequence(const std::string & name)
{
  auto invalidNameAndAbort = [&](const char * errInfo)
  {
    fprintf(stderr, "ERROR (%s) : unknown action name \'%s\' Aborting.\n", errInfo, name.c_str());

    exit(1);
  };

  std::vector<Action::BasicAction> sequence;

  char b1[1024];
  char b2[1024];
  char b3[1024];
  char b4[1024];

  if (sscanf(name.c_str(), "%s", b1) != 1)
    invalidNameAndAbort(ERRINFO);

  if(std::string(b1) == "WRITE")
  {
    if (sscanf(name.c_str(), "%s %s %s %s", b1, b4, b2, b3) != 4)
      invalidNameAndAbort(ERRINFO);

    std::string tapeName(b2);
    std::string value(b3);
    auto object = split(b4, '.');

    if (object.size() != 2)
      invalidNameAndAbort(ERRINFO);

    int relativeIndex = std::stoi(object[1]);

    if (object[0] == "b")
      sequence.emplace_back(bufferWrite(tapeName, value, relativeIndex));
    else if (object[0] == "s")
          sequence.emplace_back(stackWrite(tapeName, value, relativeIndex));     
  }
  else if(std::string(b1) == "MULTIWRITE")
  {
    int startRelIndex;
    int endRelIndex;
    
    if (sscanf(name.c_str(), "%s %d %d %s", b1, &startRelIndex, &endRelIndex, b2) != 4)
      invalidNameAndAbort(ERRINFO);

    std::string tapeName(b2);

    auto splits = split(name);

    for(int i = startRelIndex; i <= endRelIndex; i++)
      sequence.emplace_back(bufferWrite(tapeName, splits[4+i-startRelIndex], i));
  }
  else if(std::string(b1) == "RULE")
  {
    if (sscanf(name.c_str(), "%s %s ON %s %[^\n]", b1, b2, b3, b4) != 4)
      invalidNameAndAbort(ERRINFO);

    std::string targetTapeName(b2);
    std::string fromTapeName(b3);
    std::string rule(b4);

    auto apply = [fromTapeName, targetTapeName, rule](Config & c, Action::BasicAction &)
      {writeRuleResult(c, fromTapeName, targetTapeName, rule, 0);};
    auto undo = [targetTapeName](Config & c, Action::BasicAction &)
      {simpleBufferWrite(c, targetTapeName, "", 0);};
    auto appliable = [fromTapeName,rule](Config & c, Action::BasicAction &)
      {return isRuleAppliable(c, fromTapeName, 0, rule);};
    Action::BasicAction basicAction =
      {Action::BasicAction::Type::Write, rule, apply, undo, appliable};

    sequence.emplace_back(basicAction);
  }
  else if(std::string(b1) == "NOTFOUND")
  {
  }
  else if(std::string(b1) == "NOTHING")
  {
  }
  else if(std::string(b1) == "EPSILON")
  {
  }
  else if(std::string(b1) == "MOVE")
  {
    int movement;
    if (sscanf(name.c_str(), "MOVE %s %d", b2, &movement) != 2)
      invalidNameAndAbort(ERRINFO);

    sequence.emplace_back(moveHead(movement));
  }
  else if(std::string(b1) == "ERROR")
  {
    auto apply = [](Config &, Action::BasicAction &)
      {fprintf(stderr, "ERROR\n");};
    auto undo = [](Config &, Action::BasicAction &)
      {};
    auto appliable = [](Config &, Action::BasicAction &)
      {return true;};
    Action::BasicAction basicAction =
      {Action::BasicAction::Type::Push, "", apply, undo, appliable};

    sequence.emplace_back(basicAction);
  }
  else if(std::string(b1) == "CORRECT")
  {
    auto apply = [](Config &, Action::BasicAction &)
          {fprintf(stderr, "CORRECT\n");};
    auto undo = [](Config &, Action::BasicAction &)
      {};
    auto appliable = [](Config &, Action::BasicAction &)
      {return true;};
    Action::BasicAction basicAction =
      {Action::BasicAction::Type::Push, "", apply, undo, appliable};

    sequence.emplace_back(basicAction);
  }
  else if(std::string(b1) == "SHIFT")
  {
    sequence.emplace_back(pushHead());
  }
  else if(std::string(b1) == "REDUCE")
  {
    sequence.emplace_back(stackPop(true));
  }
  else if(std::string(b1) == "LEFT")
  {
    auto apply = [](Config & c, Action::BasicAction &)
      {
        int b0 = c.getHead();
        int s0 = c.stackTop();
        simpleBufferWrite(c, "GOV", std::to_string(b0-s0), s0-b0);
      };
    auto undo = [](Config & c, Action::BasicAction &)
      {
        int b0 = c.getHead();
        int s0 = c.stackTop();
        simpleBufferWrite(c, "GOV", "", s0-b0);
      };
    auto appliable = [](Config & c, Action::BasicAction &)
      {
        if (c.stackEmpty() || c.endOfTapes())
          return false;
        int b0 = c.getHead();
        int s0 = c.stackTop();
        return simpleBufferWriteAppliable(c, "GOV", s0-b0);
      };
    Action::BasicAction basicAction =
      {Action::BasicAction::Type::Write, "", apply, undo, appliable};

    sequence.emplace_back(basicAction);

    if (sscanf(name.c_str(), "%s %s", b1, b2) == 2)
    {
      auto apply2 = [b2](Config & c, Action::BasicAction &)
        {
          int b0 = c.getHead();
          int s0 = c.stackTop();
          simpleBufferWrite(c, "LABEL", b2, s0-b0);
        };
      auto undo2 = [](Config & c, Action::BasicAction &)
        {
          int b0 = c.getHead();
          int s0 = c.stackTop();
          simpleBufferWrite(c, "LABEL", "", s0-b0);
        };
      auto appliable2 = [](Config & c, Action::BasicAction &)
        {
          if (c.stackEmpty())
            return false;
          int b0 = c.getHead();
          int s0 = c.stackTop();
          return simpleBufferWriteAppliable(c, "LABEL", s0-b0);
        };
      Action::BasicAction basicAction2 =
        {Action::BasicAction::Type::Write, b2, apply2, undo2, appliable2};

          sequence.emplace_back(basicAction2);
    }

    sequence.emplace_back(stackPop(false));
  }
  else if(std::string(b1) == "RIGHT")
  {
    auto apply = [](Config & c, Action::BasicAction &)
      {
        int b0 = c.getHead();
        int s0 = c.stackTop();
        simpleBufferWrite(c, "GOV", std::to_string(s0-b0), 0);
      };
    auto undo = [](Config & c, Action::BasicAction &)
      {
        simpleBufferWrite(c, "GOV", "", 0);
      };
    auto appliable = [](Config & c, Action::BasicAction &)
      {
        return !c.stackEmpty() && !c.endOfTapes() && simpleBufferWriteAppliable(c, "GOV", 0);
      };
    Action::BasicAction basicAction =
      {Action::BasicAction::Type::Write, "", apply, undo, appliable};

    sequence.emplace_back(basicAction);

    if (sscanf(name.c_str(), "%s %s", b1, b2) == 2)
    {
      auto apply2 = [b2](Config & c, Action::BasicAction &)
        {
          simpleBufferWrite(c, "LABEL", b2, 0);
        };
      auto undo2 = [](Config & c, Action::BasicAction &)
        {
          simpleBufferWrite(c, "LABEL", "", 0);
        };
      auto appliable2 = [](Config & c, Action::BasicAction &)
        {
          return simpleBufferWriteAppliable(c, "LABEL", 0);
        };
      Action::BasicAction basicAction2 =
        {Action::BasicAction::Type::Write, b2, apply2, undo2, appliable2};

      sequence.emplace_back(basicAction2);
    }

    sequence.emplace_back(pushHead());
  }
  else if(std::string(b1) == "EOS")
  {
    auto apply0 = [b2](Config & c, Action::BasicAction &)
      {
        int b0 = c.getHead();
        int s0 = c.stackTop();
        simpleBufferWrite(c, ProgramParameters::sequenceDelimiterTape, ProgramParameters::sequenceDelimiter, s0-b0);
      };
    auto undo0 = [](Config & c, Action::BasicAction)
      {
        int b0 = c.getHead();
        int s0 = c.stackTop();
        simpleBufferWrite(c, ProgramParameters::sequenceDelimiterTape, "", s0-b0);
      };
    auto appliable0 = [](Config & c, Action::BasicAction &)
      {
        return !c.isFinal() && !c.stackEmpty();
      };
    Action::BasicAction basicAction0 =
      {Action::BasicAction::Type::Write, "", apply0, undo0, appliable0};

    sequence.emplace_back(basicAction0);
    
    auto apply = [](Config & c, Action::BasicAction & ba)
      {
        ba.data = "";
        auto & govs = c.getTape("GOV");
        int b0 = c.getHead();
        int rootIndex = -1;
        for (int i = c.stackSize()-1; i >= 0; i--)
        {
          auto s = c.stackGetElem(i);
          if (govs.getHyp(s-b0).empty() || govs.getHyp(s-b0) == "0")
          {
            if (rootIndex == -1)
              rootIndex = s;
            else
            {
              simpleBufferWrite(c, "GOV", std::to_string(rootIndex - s), s-b0);
              ba.data += "+"+std::to_string(s-b0);
            }
          }
        }

        if (rootIndex == -1)
        {
          if (c.stackEmpty())
          {
            c.printForDebug(stderr);
            fprintf(stderr, "ERROR (%s) : no suitable candidate for root. Aborting.\n", ERRINFO);
            exit(1);
          }

          rootIndex = c.stackGetElem(c.stackSize()-1);
        }

        simpleBufferWrite(c, "GOV", "0", rootIndex-b0);

        // Delete the arcs from the previous sentence to the new sentence

        auto & eos = c.getTape(ProgramParameters::sequenceDelimiterTape);

        for (int i = b0; i >= 0; i--)
        {
          if (eos[i-b0] == ProgramParameters::sequenceDelimiter)
            break;

          try
          {
            int govIndex = i + std::stoi(govs[i-b0]);
            if (govIndex <= c.stackGetElem(0))
            {
              simpleBufferWrite(c, "GOV", std::to_string(rootIndex - i), i-b0);
              simpleBufferWrite(c, "LABEL", "_", i-b0);
            }
          } catch (std::exception &) {}
        }
      };
    auto undo = [](Config & c, Action::BasicAction & ba)
      {
        auto & govs = c.getTape("GOV");
        int b0 = c.getHead();
        for (int i = c.stackSize()-1; i >= 0; i--)
        {
          auto s = c.stackGetElem(i);
          if (govs.getHyp(s-b0) == "0")
          {
            simpleBufferWrite(c, "GOV", "", s-b0);
            break;
          }
        }
        auto deps = split(ba.data, '+');
            for (auto s : deps)
          if (!s.empty())
            simpleBufferWrite(c, "GOV", "", std::stoi(s));
        ba.data.clear();
      };
    auto appliable = [](Config & c, Action::BasicAction &)
      {
        return !c.stackEmpty();
      };
    Action::BasicAction basicAction =
      {Action::BasicAction::Type::Write, "", apply, undo, appliable};

    sequence.emplace_back(basicAction);

    auto apply2 = [b2](Config & c, Action::BasicAction & ba)
      {
        ba.data = "";
        auto & labels = c.getTape("LABEL");
        int b0 = c.getHead();
        int rootIndex = -1;

        for (int i = c.stackSize()-1; i >= 0; i--)
        {
          auto s = c.stackGetElem(i);
          if (labels.getHyp(s-b0).empty())
          {
            if (rootIndex == -1)
            {
              rootIndex = 0;
              simpleBufferWrite(c, "LABEL", "root", s-b0);
            }
            else
            {
              simpleBufferWrite(c, "LABEL", "_", s-b0);
              ba.data += "+"+std::to_string(s-b0);
            }
          }
        }
      };
    auto undo2 = [](Config & c, Action::BasicAction & ba)
      {
        auto & labels = c.getTape("LABEL");
        int b0 = c.getHead();

        for (int i = c.stackSize()-1; i >= 0; i--)
        {
          auto s = c.stackGetElem(i);
          if (labels.getHyp(s-b0) == "root")
          {
            simpleBufferWrite(c, "LABEL", "", s-b0);
            break;
          }
        }
        auto deps = split(ba.data, '+');
        for (auto & dep : deps)
          if (!dep.empty())
            simpleBufferWrite(c, "LABEL", "", std::stoi(dep));
        ba.data.clear();
      };
    auto appliable2 = [](Config & c, Action::BasicAction &)
      {
        return !c.stackEmpty();
      };
    Action::BasicAction basicAction2 =
      {Action::BasicAction::Type::Write, "", apply2, undo2, appliable2};

    sequence.emplace_back(basicAction2);

    auto apply4 = [b2](Config & c, Action::BasicAction & ba)
      {
            ba.data = "";
        for (int i = c.stackSize()-1; i >= 0; i--)
        {
          auto s = c.stackGetElem(i);
          ba.data += std::to_string(s) + " ";
        }

        while (!c.stackEmpty())
          c.stackPop();
      };
    auto undo4 = [](Config & c, Action::BasicAction & ba)
      {
        auto elems = split(ba.data);
        for (auto elem : elems)
          if (!elem.empty())
            c.stackPush(std::stoi(elem));
        ba.data.clear();
      };
    auto appliable4 = [](Config & c, Action::BasicAction &)
      {
        return !c.isFinal() && !c.stackEmpty();
      };
    Action::BasicAction basicAction4 =
      {Action::BasicAction::Type::Pop, "", apply4, undo4, appliable4};

    sequence.emplace_back(basicAction4);
  }
  else if(std::string(b1) == "BACK")
  {
    if (sscanf(name.c_str(), "%s %s", b1, b2) != 2)
      invalidNameAndAbort(ERRINFO);

    if (isNum(b2))
    {
      int dist = std::stoi(b2);

      auto apply = [dist](Config & c, Action::BasicAction &)
        {
          std::string classifierName = c.pastActions.top().first;
          if (ProgramParameters::debug)
            fprintf(stderr, "classifierName = <%s>\n", classifierName.c_str());

          static auto undoOneTime = [](Config & c, const std::string & classifierName)
          {
            if (ProgramParameters::debug)
              fprintf(stderr, "classifierName = <%s>\n", classifierName.c_str());

            while (true)
            {
              auto a = c.pastActions.pop();

              a.second.undoOnlyStack(c);

              if (a.first == classifierName)
                return;
            }
          };

          static auto undoForReal = [](Config & c, const std::string & classifierName)
          {
            if (ProgramParameters::debug)
              fprintf(stderr, "classifierName = <%s>\n", classifierName.c_str());

            while (true)
            {
              if (c.pastActions.empty())
              {
                fprintf(stderr, "ERROR (%s) : trying to undo action while pastActions is empty. Aborting.\n", ERRINFO);
                exit(1);
              }
                  auto a = c.pastActions.pop();

              if (a.first == classifierName)
              {
                a.second.undo(c);
                return;
              }
              a.second.undoOnlyStack(c);
            }
          };

          undoOneTime(c, classifierName);
          for (int i = 0; i < dist-1; i++)
            undoOneTime(c, classifierName);

          undoForReal(c, classifierName);
        };
      auto undo = [dist](Config &, Action::BasicAction &)
        {
        };
      auto appliable = [dist](Config & c, Action::BasicAction)
        {
          if (c.pastActions.size() == 0)
            return false;

          if (c.getCurrentStateHistory().size() > 0 && c.getCurrentStateHistory().top() != "EPSILON")
          {
            return false;
          }

          const std::string & classifierName = c.pastActions.top().first;

          if (c.hashHistory.contains(c.computeHash()))
            return false;

          unsigned int topIndex = 0;

          static auto undoOneTime = [](Config & c, const std::string & classifierName, unsigned int & topIndex)
          {
            while (true)
            {
              topIndex++;

              if (topIndex > c.pastActions.size())
                return;

              if (c.pastActions.getElem(topIndex-1).first == classifierName)
                return;
            }
          };

          undoOneTime(c, classifierName, topIndex);
          for (int i = 0; i < dist-1; i++)
            undoOneTime(c, classifierName, topIndex);

          undoOneTime(c, classifierName, topIndex);

          if (topIndex >= c.pastActions.size())
            return false;

          return true;
        };
        Action::BasicAction basicAction =
          {Action::BasicAction::Type::Back, name, apply, undo, appliable};

        sequence.emplace_back(basicAction);
    }
    else
    {
      invalidNameAndAbort(ERRINFO);
        }
  }
  else
    invalidNameAndAbort(ERRINFO);

  return sequence;
}

void ActionBank::simpleBufferWrite(Config & config, const std::string & tapeName, 
  const std::string & value, int relativeIndex)
{
  auto & tape = config.getTape(tapeName);

  tape.setHyp(relativeIndex, value);
}

bool ActionBank::simpleBufferWriteAppliable(Config & config,
  const std::string & tapeName, int relativeIndex)
{
  auto & tape = config.getTape(tapeName);

  int index = config.getHead() + relativeIndex;

  if (config.endOfTapes())
    return true;

  return !(index < 0) && index < tape.size();
}

bool ActionBank::isRuleAppliable(Config & config,
  const std::string & tapeName, int relativeIndex, const std::string & rule)
{
  if (!simpleBufferWriteAppliable(config, tapeName, relativeIndex))
    return false;
  return ruleIsAppliable(config.getTape(tapeName)[relativeIndex], rule);
}

void ActionBank::writeRuleResult(Config & config, const std::string & fromTapeName, const std::string & targetTapeName, const std::string & rule, int relativeIndex)
{
  auto & fromTape = config.getTape(fromTapeName);
  auto & toTape = config.getTape(targetTapeName);

  auto & from = fromTape.getRef(relativeIndex);

  toTape.setHyp(relativeIndex, applyRule(from, rule));
}

int ActionBank::getLinkLength(const Config & c, const std::string & action)
{
  auto splitted = split(action, ' ');
  auto & name = splitted[0];
  if (name == "LEFT" || name == "RIGHT" || name == "EOS")
  {
    if (c.stackEmpty())
    {
      fprintf(stderr, "ERROR (%s) : stack is empty. Aborting.\n", ERRINFO);
      exit(1);
    }

    int stackIndex = c.stackGetElem(0);
    return std::abs(c.getHead() - stackIndex);
  }

  return 0;
}