// re2swift $INPUT -o $OUTPUT
import Foundation

// Unbounded number of version components.
struct Ver: Equatable { let components: [Int] }

func parse(_ yyinput: UnsafePointer<UInt8>) -> Ver? {
  let tagNone = -1

  var yycursor = 0, yymarker = 0
  var mTagPool = [MTag]()

  // Final tag variables available in semantic action.
  /*!svars:re2c format = "  let @@: Int\n"; */
  /*!mvars:re2c format = "  let @@: MTag?\n"; */

  // Intermediate tag variables used by the lexer (must be autogenerated).
  /*!stags:re2c format = "  var @@ = tagNone\n"; */
  /*!mtags:re2c format = "  var @@: MTag? = nil\n"; */

  /*!re2c
    re2c:tags = 1;
    re2c:yyfill:enable = 0;
    re2c:YYSTAGP = "@@ = yycursor";
    re2c:YYSTAGN = "@@ = tagNone";
    re2c:YYMTAGP = "@@ = add(tag: @@, value: yycursor)";
    re2c:YYMTAGN = "@@ = add(tag: @@, value: tagNone)";

    num = [0-9]+;

    @t1 num @t2 ("." #t3 num #t4)* [\x00] {
      var components = [s2n(t1..<t2)]
      unfold(&components, t3, t4)
      return Ver(components: components)
    }
    * { return nil }
  */

  // Recursively unwind tag histories and collect version components.
  func unfold(_ ver: inout [Int], _ x: MTag?, _ y: MTag?) {
    if x == nil && y == nil {
      // Reached the root of the m-tag tree, stop recursion.
      return
    }

    // Unwind history further.
    unfold(&ver, x?.prev, y?.prev)

    // Get tag values, tag histories must have equal length.
    guard let ex = x?.elem, let ey = y?.elem else {
      fatalError("mismatched history length")
    }

    guard ex != tagNone && ey != tagNone else {
      // Both tags are empty, this corresponds to zero repetitions.
      assert(ex == ey)
      return
    }

    // Both tags are valid indices, extract component.
    ver.append(s2n(ex..<ey))
  }

  // Pre-parsed string to number.
  func s2n(_ range: Range<Int>) -> Int {
    range.reduce(0) { accum, idx in
      accum * 10 + Int(yyinput[idx] - UInt8(ascii: "0"))
    }
  }

  // Append a single value to an m-tag history.
  func add(tag prevTag: MTag?, value: Int) -> MTag {
    let tag = MTag(prev: prevTag, element: value)
    mTagPool.append(tag)
    return tag
  }
}

// An m-tag tree is a way to store histories with an O(1) copy operation.
// Histories naturally form a tree, as they have common start and fork at some
// point. The tree is stored as an array of pairs (tag value, link to parent).
// An m-tag is represented with a single link in the tree (array index).
class MTag {
  weak var prev: MTag?  // Link of predecessor node or root (nil)
  var elem: Int  // Tag value

  init(prev: MTag?, element: Int) {
    self.prev = prev
    self.elem = element
  }
}

assert(parse("1") == Ver(components: [1]))
assert(parse("1.2.3.4.5.6.7") == Ver(components: [1, 2, 3, 4, 5, 6, 7]))
assert(parse("1.2.") == nil)
