Class: CDDL::Parser

Inherits:

Object

• Object
• CDDL::Parser

Defined in:

lib/cddl.rb

Defined Under Namespace

Classes: BackTrack

Constant Summary

FEATURE_REJECT_RE =

/\A\^/

REGEXP_FOR_STRING =

Memoize a bit here

Hash.new {|h, k|
  h[k] = Regexp.new("\\A(?:#{k})\\z")
}

ABNF_PARSER_FOR_STRING =

Hash.new {|h, k|
  grammar = "cddl-t0p--1eve1-f0r--abnf = " << k # XXX
  h[k] = ABNF.from_abnf(grammar)
}

ABNF_ENCODING_FOR_CONOP =

{
  abnf: Encoding::UTF_8,
  abnfb: Encoding::BINARY
}

VALUE_TYPE =

{text: String, bytes: String, int: Integer, float: Float}

SIMPLE_VALUE =

{
  [:prim, 7, 20] => [true, false, :bool],
  [:prim, 7, 21] => [true, true, :bool],
  [:prim, 7, 22] => [true, nil, :nil],
  [:prim, 7, 23] => [true, :undefined, :undefined],
}

OPERATORS =

{lt: :<, le: :<=, gt: :>, ge: :>=, eq: :==, ne: :!=}

Instance Attribute Summary

• #ast ⇒ Object readonly

  Returns the value of attribute ast.

Instance Method Summary

• #apr ⇒ Object

  for debugging.

• #ast_debug ⇒ Object
• #cname(s) ⇒ Object
• #defines(prefix) ⇒ Object

  Generate some simple #define lines from the value-only rules.

• #extract_arg0(t) ⇒ Object
• #extract_array(t) ⇒ Object
• #extract_feature(control, d) ⇒ Object
• #extract_value(t) ⇒ Object

  [].

• #generate ⇒ Object
• #generate1(where, inmap = false) ⇒ Object
• #initialize(source_text) ⇒ Parser constructor

  A new instance of Parser.

• #lookup_recurse_grpent(name) ⇒ Object
• #map_check(d, d_check, members) ⇒ Object
• #remove_indentation(s) ⇒ Object
• #rules ⇒ Object
• #strip_nodes(n) ⇒ Object
• #try_generate(target) ⇒ Object
• #unpack_array_to_sequence(content, where) ⇒ Object
• #validate(d, warn = true) ⇒ Object
• #validate1(d, where) ⇒ Object
• #validate1a(d, where) ⇒ Object
• #validate_diag ⇒ Object
• #validate_forward(d, start, where) ⇒ Object
• #validate_linear(d, start, where) ⇒ Object

  returns number of matches or false for breakage.

• #validate_result(check) ⇒ Object
• #walk(rule, anno = nil, &block) ⇒ Object

Constructor Details

#initialize(source_text) ⇒ Parser

Returns a new instance of Parser.

# File 'lib/cddl.rb', line 45

def initialize(source_text)
  @abnf = Peggy::ABNF.new
  _cresult = @abnf.compile! ABNF_SPEC, ignore: :s
  presult = @abnf.parse? :cddl, (source_text + PRELUDE)
  expected_length = source_text.length + PRELUDE.length
  if expected_length != presult
    upto = @abnf.parse_results.keys.max
    puts "UPTO: #{upto}" if $advanced
    pp @abnf.parse_results[upto] if $advanced
    pp @abnf.parse_results[presult] if $advanced
    puts "SO FAR: #{presult}"  if $advanced
    puts @abnf.ast? if $advanced
    presult ||= 0
    part1 = source_text[[presult - 100, 0].max...presult]
    part3 = source_text[upto...[upto + 100, source_text.length].min]
    if upto - presult < 100
      part2 = source_text[presult...upto]
    else
      part2 = source_text[presult, 50] + "......." + source_text[upto-50, 50]
    end
    warn "*** Look for syntax problems around the #{
           "%%%".colorize(background: :light_yellow)} markers:\n#{
           part1}#{"%%%".colorize(color: :green, background: :light_yellow)}#{
           part2}#{"%%%".colorize(color: :red, background: :light_yellow)}#{
           part3}"
    raise ParseError, "*** Parse error at #{presult} upto #{upto} of #{
                      source_text.length} (#{expected_length})."
  end
  puts @abnf.ast? if $debug_ast
  @ast = @abnf.ast?
  # our little argument stack for rule processing
  @insides = []
  # collect error information
  @last_message = ""
end

Instance Attribute Details

#ast ⇒ Object (readonly)

Returns the value of attribute ast.

# File 'lib/cddl.rb', line 1265

def ast
  @ast
end

Instance Method Details

#apr ⇒ Object

for debugging

# File 'lib/cddl.rb', line 81

def apr                     # for debugging
  @abnf.parse_results
end

#ast_debug ⇒ Object

# File 'lib/cddl.rb', line 85

def ast_debug
  ast.to_s[/.*comment/m]    # stop at first comment -- prelude
end

#cname(s) ⇒ Object

# File 'lib/cddl.rb', line 120

def cname(s)
  s.to_s.gsub(/-/, "_")
end

#defines(prefix) ⇒ Object

Generate some simple #define lines from the value-only rules

# File 'lib/cddl.rb', line 125

def defines(prefix)
  prefix ||= "CDDL"
  if prefix =~ /%\d*\$?s/
    format = prefix
    format += "\n" unless format[-1] == "\n"
  else
    format = "#define #{prefix}_%s %s\n"
  end
  s = {}                    # keys form crude set of defines
  add = proc { |*a| s[format % a] = true }
  r = rules
  ast.each :rule do |rule|
    if rulename = rule.typename
      t = rule.type.children(:type1)
      if t.size == 1
        if (t2 = t.first.children(:type2)) && t2.size == 1 && (v = t2.first.value)
          add.(cname(rulename), v.to_s)
        end
      end
    end
  end
  # CBOR::PP.pp r
  walk(r) do |subtree, anno|
    if subtree[0] == :type1 && subtree[1..-1].all? {|x| x[0] == :int}
      if enumname = subtree.cbor_annotations rescue nil
        enumname = cname(enumname.first)
        subtree[1..-1].each do |x|
          if memname = x.cbor_annotations
            memname = "#{enumname}_#{cname(memname.first)}"
            add.(memname, x[1].to_s)
          end
        end
      end
    end
    if subtree[0] == :array
      if (arrayname = subtree.cbor_annotations rescue nil) || anno
        arrayname = cname(arrayname ? arrayname.first : anno)
        subtree[1..-1].each_with_index do |x, i|
          if x[0] == :member
            if Array === x[3] && x[3][0] == :text
              memname = x[3][1] # preferably use key string
            elsif memname = x[4].cbor_annotations
              memname = memname.first # use value annotation otherwise
            end
            if memname
              memname = "#{arrayname}_#{cname(memname)}_index"
              add.(memname, i.to_s)
            end
          end
          if x[0] == :member && (x[1] != 1 || x[2] != 1)
            break           # can't give numbers if we have optionals etc.
          end
        end
      end
    end
  end
  s.keys.join
end

#extract_arg0(t) ⇒ Object

# File 'lib/cddl.rb', line 754

def extract_arg0(t)
  return [false] unless t[0] == :array
  [true,
   (el = t[1]
    return [false] unless el[0..3] == [:member, 1, 1, nil]
    ok, v, vt = extract_value(el[4])
    return [false] unless ok
    [v, vt]
   ),
   *t[2..-1]]
end

#extract_array(t) ⇒ Object

# File 'lib/cddl.rb', line 743

def extract_array(t)
  return [false] unless t[0] == :array
  [true, *t[1..-1].map { |el|
     return [false] unless el[0..3] == [:member, 1, 1, nil]
     ok, v, vt = extract_value(el[4])
     return [false] unless ok
     [v, vt]
   }]
end

#extract_feature(control, d) ⇒ Object

# File 'lib/cddl.rb', line 766

def extract_feature(control, d)
  ok, v, vt = extract_value(control)
  if ok
    nm = v
    det = d
    warn "*** feature controller should be a string: #{control.inspect}" unless String == vt
  else
    ok, *v = extract_array(control)
    if ok && v.size == 2
      nm = v[0][0]
      det = v[1][0]
      warn "*** first element of feature controller should be a string: #{control.inspect}" unless String === nm
    else
      warn "*** feature controller not implemented: #{control.inspect}"
    end
  end
  [nm, det]
end

#extract_value(t) ⇒ Object

# File 'lib/cddl.rb', line 714

def extract_value(t)        # []
  if vt = VALUE_TYPE[t[0]]
    [true, t[1], vt]
  elsif v = SIMPLE_VALUE[t]
    v
  elsif t[0] == :anno
    _, conop, target, control = t
    # warn ["EXV0", conop, target, control].inspect
    if conop == :cat || conop == :plus || conop == :det
      ok1, v1, vt1 = extract_value(target)
      ok2, v2, vt2 = extract_value(control)
      # warn ["EXV", ok1, v1, vt1, ok2, v2, vt2].inspect
      if ok1 && ok2
        if vt1 == Integer
          [true, v1 + Integer(v2), Integer] if vt2 == Integer || vt2 == Float
        elsif vt1 == Float
          [true, v1 + v2, vt1] if vt2 == Integer || vt2 == Float
        else
          if conop == :det
            v1 = remove_indentation(v1)
            v2 = remove_indentation(v2)
          end
          [true, v1 + v2, vt1] if vt1 == vt2
        end
      end rescue nil
    end
  end || [false]
end

#generate ⇒ Object

# File 'lib/cddl.rb', line 304

def generate
  @recursion = 0
  generate1(rules)
end

#generate1(where, inmap = false) ⇒ Object

# File 'lib/cddl.rb', line 309

def generate1(where, inmap = false)
  case where[0]
  when :type1
    fail BackTrack.new("Can't generate from empty type choice socket yet") unless where.size > 1
    begin
      chosen = where[rand(where.size-1)+1]
      generate1(chosen)
    rescue BackTrack
      tries = where[1..-1].sample(where.size) - [chosen]
      r = begin
            if tries.empty?
              BackTrack.new("No suitable alternative in type choice")
            else
              generate1(tries.pop)
            end
          rescue BackTrack
            retry
          end
      fail r if BackTrack === r
      r
    end
  when :grpchoice
    fail BackTrack.new("Can't generate from empty group choice socket yet") unless where.size > 1
    begin
      chosen = where[rand(where.size-1)+1]
      chosen.flat_map {|m| generate1(m, inmap)}
    rescue BackTrack
      tries = where[1..-1].sample(where.size) - [chosen]
      r = begin
            if tries.empty?
              BackTrack.new("No suitable alternative in group choice")
            else
              tries.pop.flat_map {|m| generate1(m, inmap)}
            end
          rescue BackTrack
            retry
          end
      fail r if BackTrack === r
      r
    end
  when :map
    Hash[where[1..-1].flat_map {|m| generate1(m, true)}]
  when :recurse_grpent
    name = where[1]
    rule = lookup_recurse_grpent(name)
    if @recursion < MAX_RECURSE
      @recursion += 1
#p ["recurse_grpent", *rule]
#r = generate1(rule)
      r = rule[1..-1].flat_map {|m| generate1(m, inmap)}
      @recursion -= 1
      r
    else
      fail "Deep recursion into #{name}: #{@stage1[name]}, not yet implemented"
    end
  when :array, :grpent
    r = where[1..-1].flat_map {|m| generate1(m).map{|e| e[1]}}
        .flat_map {|e| Array === e && e[0] == :grpent ? e[1..-1] : [e]}
                       # nested grpents need to be "unpacked"
    if where[0] == :grpent
      [:grpent, *r]
    else
      r
    end
  when :member
    st = where[1]
    fudge = 4 * (1 - (@recursion / MAX_RECURSE.to_f))**3 # get less generate-happy with more recursion
    en = [where[2], [st, fudge].max].min # truncate to fudge unless must be more
    st += rand(en + 1 - st) if en != st
    kr = where[3]
    vr = where[4]
    if inmap
      unless kr
        case vr[0]
        when :grpent
          # fail "grpent in map #{vr.inspect}" unless vr.size == 2
          g = Array.new(st) {
            vr[1..-1].map{ |vrx|
              generate1(vrx, true)
            }.flatten(1)
          }.flatten(1)
          # warn "GGG #{g.inspect}"
          return g
        when :grpchoice
          g = Array.new(st) { generate1(vr, true) }.flatten(1)
          # warn "GGG #{g.inspect}"
          return g
        else
          fail "member key not given in map for #{where}"  # || vr == [:grpchoice]
        end
      end
    end
    begin
      Array.new(st) { [ (generate1(kr) if kr), # XXX: need error in map context
                        generate1(vr)
                      ]}
    rescue BackTrack
      fail BackTrack.new("Need #{where[1]}..#{where[2]} of these: #{[kr, vr].inspect}") unless where[1] == 0
      []
    end
  when :text, :int, :float, :bytes
    where[1]
  when :range
    rand(where[1])
  when :prim
    case where[1]
    when nil
      gen_word              # XXX: maybe always returning a string is confusing
    when 0
      rand(4711)
    when 1
      ~rand(815)
    when 2
      gen_word.force_encoding(Encoding::BINARY)
    when 3
      gen_word
    when 6
      tn = Integer === where[2] ? where[2] : generate1(where[2])
      unless Integer === tn && tn >= 0
        fail "Can't generate a tag number out of #{where[2]}"
      end
      CBOR::Tagged.new(tn, generate1(where[3]))
    when 7
      case where[2]
      when nil
        Math::PI
      when 20
        false
      when 21
        true
      when 22
        nil
      when 23
        :undefined
      when 25, 26, 27
        rand()
      end
    else
      fail "Can't generate prim #{where[1]}"
    end
  when :anno
    target = where[2]
    control = where[3]
    case conop = where[1]
    when :size
      should_be_int = generate1(control)
      unless (Array === target && target[0] == :prim && [0, 2, 3].include?(target[1])) && Integer === should_be_int && should_be_int >= 0
        fail "Don't know yet how to generate #{where}"
      end
      s = Random.new.bytes(should_be_int)
      case target[1]
      when 0
        # silently restrict to what we can put into a uint
        s[0...8].bytes.inject(0) {|a, b| a << 8 | b }
      when 2
        s
      when 3
        Base64.urlsafe_encode64(s)[0...should_be_int]
        # XXX generate word a la w = gen_word
      end
    when :bits
      set_of_bits = Array.new(10) { generate1(control) } # XXX: ten?
      # p set_of_bits
      unless (target == [:prim, 0] || target == [:prim, 2]) &&
             set_of_bits.all? {|x| Integer === x && x >= 0 }
        fail "Don't know yet how to generate #{where}"
      end
      if target == [:prim, 2]
        set_of_bits.inject(String.new) do |s, i|
          n = i >> 3
          bit = 1 << (i & 7)
          if v = s.getbyte(n)
            s.setbyte(n, v | bit); s
          else
            s << "\0" * (n - s.size) << bit.chr(Encoding::BINARY)
          end
        end
      else                  # target == [:prim, 0]
        set_of_bits.inject(0) do |a, v|
          a |= (1 << v)
        end
      end
    when :default
      # Hmm.
      unless $default_warned
        warn "*** Ignoring .default for now."
        $default_warned = true
      end
      generate1(target, inmap)
    when :feature
      feature, = extract_feature(control, nil)
      # warn "@@@ GENFEAT #{feature.inspect} #{CDDL_FEATURE_REJECT[feature].inspect}"
      if CDDL_FEATURE_REJECT[feature]
        fail BackTrack.new("Feature '#{feature}' rejected")
      end
      generate1(target, inmap)
    when :cat, :det
      lhs = generate1(target, inmap)
      rhs = generate1(control)
      if conop == :det
        lhs = remove_indentation(lhs)
        rhs = remove_indentation(rhs)
      end
      begin
        lhs + rhs
      rescue Exception => e
        fail "Can't #{lhs.inspect} .cat #{rhs.inspect}: #{e.message}"
      end
    when :plus
      lhs = generate1(target, inmap)
      rhs = generate1(control)
      begin
        case lhs
        when Integer
          lhs + Integer(rhs)
        when Numeric
          lhs + rhs
        else
          fail "#{lhs.inspect}: Not a number"
        end
      rescue Exception => e
        fail "Can't #{lhs.inspect} .plus #{rhs.inspect}: #{e.message}"
      end
    when :eq
      content = generate1(control)
      if validate1(content, where)
        return content
      end
      fail "Not smart enough to generate #{where}"
    when :lt, :le, :gt, :ge, :ne
      if Array === target && target[0] == :prim
        content = generate1(control)
        try = if Numeric === content
                content = Integer(content)
                case target[1]
                when 0
                  case conop
                  when :lt
                    rand(0...content)
                  when :le
                    rand(0..content)
                  end
                end
              end
        if validate1(try, where)
          return try
        else
          warn "HUH gen #{where.inspect} #{try.inspect}" unless try.nil?
        end
      end
      try_generate(target) do |content|
        if validate1(content, where)
          return content
        end
      end
      fail "Not smart enough to generate #{where}"
    when :regexp
      regexp = generate1(control)
      unless target == [:prim, 3] && String === regexp
        fail "Don't know yet how to generate #{where}"
      end
      REGEXP_FOR_STRING[regexp].random_example(max_repeater_variance: 5)
    when :abnf, :abnfb
      grammar = generate1(control)
      bytes = true if target == [:prim, 2]
      bytes = false if target == [:prim, 3]
      unless !bytes.nil? && String === grammar
        fail "Don't know yet how to generate #{where}"
      end
      grammar << "\n" unless grammar =~ /\n\z/
      out = ABNF_PARSER_FOR_STRING[grammar].generate
      if conop == :abnfb
        out = out.codepoints.pack("C*")
      end
      enc = bytes ? Encoding::BINARY : Encoding::UTF_8
      out.force_encoding(enc)
    when :cbor, :cborseq, :cbordet, :cborseqdet
      unless target == [:prim, 2]
        fail "Don't know yet how to generate #{where}"
      end
      input = generate1(control)
      if conop == :cbordet || conop == :cborseqdet
        input = input.cbor_prepare_deterministic
      end
      content = CBOR::encode(input)
      if conop == :cborseq || conop == :cborseqdet
        # remove the first head
        content = unpack_array_to_sequence(content, where)
      end
      content
    when :json
      unless target == [:prim, 3]
        fail "Don't know yet how to generate #{where}"
      end
      content = JSON::dump(generate1(control))
      content
    when :decimal
      unless target == [:prim, 3]
        fail "Don't know yet how to generate #{where}"
      end
      content = Integer(generate1(control)).to_s
      content
    when :join
      try_generate(control) do |content|
        if Array === content &&
           content.all? {|x| String === x} &&
           Set[content.map {|x| x.encoding}].size == 1
          content = content.join
          if validate1(content, target)
            return content
          end
        end
      end
      fail "Don't know yet how to generate #{where}"
    when :b64u, :"b64u-sloppy", :b64c, :"b64c-sloppy",
         :b45, :b32, :h32, :hex, :hexlc, :hexuc
      try_generate(control) do |content|
        if String === content
          content = case conop
                when :b64u, :"b64u-sloppy"
                  Base64.urlsafe_encode64(content, padding: false)
                when :b64c, :"b64c-sloppy"
                  Base64.strict_encode64(content)
                when :b45
                  Base45Lite.encode(content)
                when :b32
                  Base32.table = "ABCDEFGHIJKLMNOPQRSTUVWXYZ234567"
                  Base32.encode(content).gsub("=", "")
                when :h32
                  Base32.table = "0123456789ABCDEFGHIJKLMNOPQRSTUV"
                  Base32.encode(content).gsub("=", "")
                when :hex, :hexuc
                  content.unpack("H*")[0].upcase
                when :hexlc
                  content.unpack("H*")[0]
                else fail "Cannot happen"
                end
          if validate1(content, target)
            return content
          end
        end
      end
      fail "Not smart enough to generate #{where}"
    when :printf
      try_generate(control) do |content|
        if Array === content && content.size >= 1
          fmt, *data = content
          if String === fmt
            begin
              content = fmt % data
              if validate1(content, target)
                return content
              end
            rescue ArgumentError => e
              # be verbose about mismatches here
              @last_message << "\n** #{fmt.inspect} ArgumentError #{e}"
            end
          end
        end
      end
      fail "Not smart enough to generate #{where}#{@last_message}"
    when :within, :and
      try_generate(target) do |content|
        if validate1(content, control)
          return content
        elsif conop == :within
          warn "*** #{content.inspect} meets #{target.inspect} but not #{control.inspect}"
        end
      end
      fail "Not smart enough to generate #{where}"
    else
      fail "Don't know yet how to generate from #{where}"
    end
  when :recurse
    name = where[1]
    rule = @stage1[name]
    if @recursion < MAX_RECURSE
      @recursion += 1
#p ["recurse", *rule]
      r = generate1(rule)
      @recursion -= 1
      r
    else
      fail "Deep recursion into #{name}: #{@stage1[name]}, not yet implemented"
    end
  else
    fail "Don't know how to generate from #{where[0]} in #{where.inspect}"
  end
end

#lookup_recurse_grpent(name) ⇒ Object

# File 'lib/cddl.rb', line 260

def lookup_recurse_grpent(name)
  rule = @stage1[name]
  # pp rule
  fail unless rule.size == 2
  [rule[0], *rule[1]]
end

#map_check(d, d_check, members) ⇒ Object

# File 'lib/cddl.rb', line 868

def map_check(d, d_check, members)
  anno = []
  anno if members.all? { |r|
    puts "ALL SUBRULE: #{r.inspect}"         if ENV["CDDL_TRACE"]
    t, s, e, k, v = r
    case t
    when :recurse_grpent
      rule = lookup_recurse_grpent(s)
      if ann2 = map_check(d, d_check, rule[1..-1])
        anno.concat(ann2)
      end
    when :grpchoice
      r[1..-1].any? {|cand|
        puts "CHOICE SUBRULE: #{cand.inspect}"         if ENV["CDDL_TRACE"]
        cand_d_check = d_check.dup
        if ann2 = map_check(d, cand_d_check, cand)
          puts "CHOICE SUBRULE SUCCESS: #{cand.inspect}"         if ENV["CDDL_TRACE"]
          d_check.replace(cand_d_check)
          anno.concat(ann2)
        end
      }
    when :member
      unless k
        case v[0]
        when :grpent
          entries = v[1..-1]
        when :grpchoice
          entries = [v]
        else
          fail "member name not known for group entry #{r} in map"
        end
        d_check1 = d_check.dup
        occ = 0
        ann2 = []
        while occ < e && (ann3 = map_check(d, d_check1, entries)) && ann3 != []
          occ += 1
          ann2.concat(ann3)
        end
        if occ >= s
          d_check.replace(d_check1)
          anno.concat(ann2)
          puts "OCC SATISFIED: #{occ.inspect} >= #{s.inspect}" if ENV["CDDL_TRACE"]
          anno
        else
          # leave some diagnostic breadcrumbs?
          puts "OCC UNSATISFIED: #{occ.inspect} < #{s.inspect}" if ENV["CDDL_TRACE"]
          false
        end
      else
      # this is mostly quadratic; let's do the linear thing if possible
      simple, simpleval = extract_value(k)
      if simple
                      puts "SIMPLE: #{d_check.inspect} #{simpleval}"         if ENV["CDDL_TRACE"]
        # add occurrence check; check that val is present in the first place
        actual = d.fetch(simpleval, :not_found)
        if actual == :not_found
          s == 0          # minimum occurrence must be 0 then
        else
          if (ann2 = validate1a(actual, v)) &&
             d_check.delete(simpleval) {:not_found} != :not_found
            anno.concat(ann2)
          end
        end
      else
                      puts "COMPLEX: #{k.inspect} #{simple.inspect} #{simpleval.inspect}"         if ENV["CDDL_TRACE"]
        keys = d_check.keys
        ta, keys = keys.partition{ |key| validate1(key, k)}
        count = 0
        catch :enough do
          ta.all? { |val|
            if (ann2 = validate1a(d[val], v)) && # XXX check cut or not!
               d_check.delete(val) {:not_found} != :not_found
              anno.concat(ann2)
              throw :enough, true if (count += 1) == e
              true
            end
          }
        end and validate_result(count >= s) { "not enough #{ta.inspect} for #{r.inspect}" }
      end
      end
    else
      fail "Cannot validate #{t} in maps yet #{r}" # MMM
    end
  }
end

#remove_indentation(s) ⇒ Object

# File 'lib/cddl.rb', line 267

def remove_indentation(s)
  l = s.lines
  indent = l.grep(/\S/).map {|l| l[/^\s*/].size}.min
  l.map {|l| l.sub(/^ {0,#{indent}}/, "")}.join
end

#rules ⇒ Object

# File 'lib/cddl.rb', line 184

def rules
  @rules = {}
  @generics = {}
  @bindings = [{}]
  ast.each :rule do |rule|
    rule_ast =
      if rulename = rule.groupname
        [:grpent, rule.grpent]
      elsif rulename = rule.typename
        [:type1, *rule.type.children(:type1)]
      else
        fail "Huh?"
      end
    n = rulename.to_s
    asg = rule.assign.to_s
    if g = rule.genericparm
      if asg != "="
        fail "Augment #{asg.inspect} not implemented for generics"
      end
      ids = g.children(:id).map(&:to_s)
      # puts ["ids", ids].inspect
      if b = @generics[n]
        fail "Duplicate generics definition #{n} as #{rule_ast} (was #{b})"
      end
      @generics[n] = [rule_ast, ids]
    else
      case asg
      when "="
        if @rules[n]
          a = strip_nodes(rule_ast).inspect
          b = strip_nodes(@rules[n]).inspect
          if a == b
            warn "*** Warning: Identical redefinition of #{n} as #{a}"
          else
            fail "Duplicate rule definition #{n} as #{b} (was #{a})"
          end
        end
        @rules[n] = rule_ast
      when "/="
        @rules[n] ||= [:type1]
        fail "Can't add #{rule_ast} to #{n}" unless rule_ast[0] == :type1
        # XXX need to check existing rule as well
        @rules[n].concat rule_ast[1..-1]
        # puts "#{@rules[n].inspect} /="
      when "//="
        @rules[n] ||= [:grpchoice]
        fail "Can't add #{rule_ast} to #{n}" unless rule_ast[0] == :grpent
        # XXX need to check existing rule as well
        if @rules[n][0] == :grpent # widen
          @rules[n] = [:grpchoice, @rules[n]]
        end
        @rules[n] << rule_ast
        # puts "#{@rules[n].inspect} //="
      else
        fail "Unknown assign #{asg.inspect}"
      end
    end
  end
  # pp @generics
  @rootrule = @rules.keys.first # DRAFT: generics are ignored here.
  # now process the rules...
  @stage1 = {}
  result = r_process(@rootrule, @rules[@rootrule])
  r_process("used_in_cddl_prelude", @rules["used_in_cddl_prelude"])
  @rules.each do |n, r|
  #   r_process(n, r)     # debug only loop
    warn "*** Unused rule #{n}" unless @stage1[n]
  end
  if result[0] == :grpent
    warn "Group at top -- first rule must be a type!"
  end
  # end
  # @stage1
  result
end

#strip_nodes(n) ⇒ Object

# File 'lib/cddl.rb', line 89

def strip_nodes(n)
  [n[0], *n[1..-1].map {|e|
    e._strip
  }]
end

#try_generate(target) ⇒ Object

# File 'lib/cddl.rb', line 699

def try_generate(target)
  32.times do
    content = generate1(target)
    yield content           # should return if success
  end
end

#unpack_array_to_sequence(content, where) ⇒ Object

# File 'lib/cddl.rb', line 273

def unpack_array_to_sequence(content, where)
  # remove the first head
  n = case content.getbyte(0) - (4 << 5)
      when 0..23; 1
      when 24; 2
      when 25; 3
      when 26; 5
      when 27; 9      # unlikely :-)
      else fail ".cborseq sequence for #{where} not an array"
      end
  content[0...n] = ''
  content
end

#validate(d, warn = true) ⇒ Object

# File 'lib/cddl.rb', line 789

def validate(d, warn=true)
  @recursion = 0
  $features = Hash.new {|h, k| h[k] = {}}
  result = validate1a(d, rules)
  if warn
    if result
      if $features != {}
        features = $features.reject {|k, v| CDDL_FEATURE_OK[k.to_s] }
        # warn "@@@ FEAT #{CDDL_FEATURE_OK.inspect} #{CDDL_FEATURE_REJECT.inspect}"
        warn "** Features potentially used (#$fn): #{features.map {|k, v| "#{k}: #{v.keys}"}.join(", ")}" if features != {}
      end
    else
      warn "CDDL validation failure (#{result.inspect} for #{d.inspect}):"
      PP::pp(validate_diag, STDERR)
      puts(validate_diag.cbor_diagnostic)
    end
  end
  result
end

#validate1(d, where) ⇒ Object

# File 'lib/cddl.rb', line 967

def validate1(d, where)
  if ENV["CDDL_TRACE"]
    puts "DATA: #{d.inspect}"
    puts "RULE: #{where.inspect}"
  end
  # warn ["val1", d, where].inspect
  @last_data = d
  @last_rule = where
  ann = nil
  case where[0]
  when :type1
    if where[1..-1].any? {|r| ann = validate1a(d, r)}
      ann
    end
  when :map
    if Hash === d
      d_check = d.dup
      if (ann = map_check(d, d_check, where[1..-1])) && d_check == {}
        ann
      else
        if ENV["CDDL_TRACE"]
          puts "MAP RESIDUAL: #{d_check.inspect} for #{where[1..-1]} and #{d.inspect}"
        end
      end
    end
  when :array
    # warn ["valarr", d, where].inspect
    if Array === d
      # validate1 against the record
      idx, ann = validate_forward(d, 0, where)
      ann if validate_result(idx == d.size) { "#{validate_diag.inspect} -- cannot complete (#{idx}, #{d.size}) array #{d} for #{where}" }
    end
  when :int, :float
    _, v = extract_value(where)
    [] if d == v
  when :text, :bytes
    _, v = extract_value(where)
    [] if d == v && ((d.encoding == Encoding::BINARY) == (v.encoding == Encoding::BINARY))
  when :range
    [] if where[2] === d && where[1].include?(d)
  when :anno
    _, conop, target, control = where
    if conop == :cat || conop == :plus || conop == :det
      ok1, v1, vt1 = extract_value(target)
      ok2, v2, vt2 = extract_value(control)
      # warn ["ANNO0", ok1, v1, vt1, ok2, v2, vt2, d].inspect
      if ok1 && ok2
        v2 = Integer(v2) if vt1 == Integer
        if conop == :det
          v1 = remove_indentation(v1)
          v2 = remove_indentation(v2)
        end
        # warn ["ANNO", ok1, v1, vt1, ok2, v2, vt2, d].inspect
        [] if d == v1 + v2  # XXX Focus ArgumentError
      end
    elsif ann = validate1a(d, target)
      case conop
      when :size
        case d
        when Integer
          ok, v, vt = extract_value(control)
          if ok && vt == Integer
            ann if (d >> (8*v)) == 0
          end
        when String
          ann if validate1(d.bytesize, control)
        end
      when :bits
        if String === d
          d.each_byte.with_index.all? { |b, i|
            bit = i << 3
            ann if 8.times.all? { |nb|
              b[nb] == 0 || validate1(bit+nb, control)
            }
          }
        elsif Integer === d
          if d >= 0
            ok = true
            i = 0
            while ok && d > 0
              if d.odd?
                ok &&= validate1(i, control)
              end
              d >>= 1; i += 1
            end
            ann if ok
          end
        end
      when :default
        # Hmm.
        unless $default_warned
          warn "*** Ignoring .default for now."
          $default_warned = true
        end
        ann
      when :feature
        nm, det = extract_feature(control, d)
        $features[nm][det] = true
        ann if !CDDL_FEATURE_REJECT[nm]
      when :lt, :le, :gt, :ge, :eq, :ne
        op = OPERATORS[conop]
        ok, v, _vt = extract_value(control)
        if ok
          ann if d.send(op, v) rescue nil # XXX Focus ArgumentError
        end
      when :regexp
        ann if (
        if String === d
          ok, v, vt = extract_value(control)
          if ok && vt == String
            re = REGEXP_FOR_STRING[v]
            # pp re
            d.match(re)
          end
        end
        )
      when :abnf, :abnfb
        ann if (
        if String === d
          ok, v, vt = extract_value(control)
          if ok && vt == String
            begin
              ABNF_PARSER_FOR_STRING[v].validate(
                d.dup.force_encoding(ABNF_ENCODING_FOR_CONOP[conop]).codepoints.pack("U*")
              )
              true
            rescue => e
              # warn "*** #{e}" # XXX
              @last_message = e.to_s.force_encoding(Encoding::UTF_8)
              nil
            end
          end
        end
        )
      when :cbor
        ann if validate1((CBOR::decode(d) rescue :BAD_CBOR), control)
      when :cborseq
        ann if validate1((CBOR::decode("\x9f".b << d << "\xff".b) rescue :BAD_CBOR), control)
      when :cbordet
        decoded = CBOR::decode(d) rescue :BAD_CBOR
        if d != decoded.to_deterministic_cbor
          @last_message = "CBOR #{d.inspect} not deterministically encoded"
          nil
        else
          ann if validate1(decoded, control)
        end
      when :cborseqdet
        decoded = CBOR::decode("\x9f".b << d << "\xff".b) rescue :BAD_CBOR
        if d != unpack_array_to_sequence(decoded.to_deterministic_cbor, d.inspect)
          @last_message = "CBOR Sequence #{d.inspect} not deterministically encoded"
          nil
        else
          ann if validate1(decoded, control)
        end
      when :json
        ann if validate1((JSON::load(d) rescue :BAD_JSON), control)
      when :decimal
        ann if (
            if /\A0|-?[1-9][0-9]*\z/ === d
              validate1((d.to_i rescue :BAD_JSON), control)
            end
          )
      when :join
        ok, *v = extract_array(control)
        # warn "@@@JJJ@@@ #{ok.inspect} #{v.inspect}"
        if ok
          expected = v.map {|ve|
            fail "Not a string in #{where}" unless String === ve[0]
            ve[0]
          }.join
          ann if d == expected
        else
          fail "Don't know yet how to validate against #{where}"
        end
      when :b64u, :"b64u-sloppy", :b64c, :"b64c-sloppy", :b45, :b32, :h32, :hex, :hexlc, :hexuc
        ann if (
            String === d && (
            decoded = case conop
                when :b64u
                  /=/ !~ d &&
                  Base64.urlsafe_decode64(d)
                when :"b64u-sloppy"
                  /[-_=]/ !~ d &&
                  Base64.decode64(d.tr("+/", "-_"))
                when :b64c
                  Base64.strict_decode64(d)
                when :"b64c-sloppy"
                  Base64.decode64(d)
                when :b32
                  /=/ !~ d &&
                    (Base32.table = "ABCDEFGHIJKLMNOPQRSTUVWXYZ234567") &&
                    Base32.decode(d)
                when :b45
                  Base45Lite.decode(d)
                when :h32
                  /=/ !~ d &&
                    (Base32.table = "0123456789ABCDEFGHIJKLMNOPQRSTUV") &&
                    Base32.decode(d)
                when :hex
                  /\A[0-9a-fA-F]*\z/ =~ d && [d].pack("H*")
                when :hexuc
                  /\A[0-9A-F]*\z/ =~ d && [d].pack("H*")
                when :hexlc
                  /\A[0-9a-f]*\z/ =~ d && [d].pack("H*")
                else fail "Cannot happen"
                end
            ) && validate1(decoded.b, control)
          )
      when :printf
        ann if String === d && (
                 ok, fmt, *v = extract_arg0(control)
                 if ok && String == fmt[1]
                   fmt = fmt[0]
                   # warn "** ok #{ok.inspect} fmt #{fmt.inspect} v #{v.inspect}"
                   decoded = d.scanf(fmt) # this is a bit too lenient, so let's do:
                   encode_again = fmt % decoded
                   if encode_again != d
                     warn "** fmt #{fmt.inspect} d #{d.inspect} decoded #{decoded.inspect} encode_again #{encode_again.inspect}"
                   else
                     validate1(decoded, [:array, *v])
                   end
                 end
               )
      when :within
        if validate1(d, control)
          ann
        else
          warn "*** #{d.inspect} meets #{target} but not #{control}"
          nil
        end
      when :and
        ann if validate1(d, control)
      else
        fail "Don't know yet how to validate against #{where}"
      end
    end
  when :prim
    # warn "validate prim WI #{where.inspect} #{d.inspect}"
    case where[1]
    when nil
      true
    when 0
      Integer === d && d >= 0 && d <= 0xffffffffffffffff
    when 1
      Integer === d && d < 0 && d >= -0x10000000000000000
    when 2
      String === d && d.encoding == Encoding::BINARY
    when 3
      String === d && d.encoding != Encoding::BINARY # cheat
    when 6
      if Integer === d
        t = 2               # assuming only 2/3 match an Integer
        if d < 0
          d = ~d
          t = 3
        end
        d = CBOR::Tagged.new(t, d == 0 ? "".b : d.digits(256).reverse!.pack("C*"))
      end
      CBOR::Tagged === d && (
        Integer === where[2] ? d.tag == where[2] : validate1a(d.tag, where[2])
      ) && validate1a(d.data, where[3])
    when 7
      t, v = extract_value(where)
      if t
        v.eql? d
      else
        case where[2]
        when nil
          # XXX
          fail
        when 25, 26, 27
          Float === d
        else
          fail
        end
      end
    else
      fail "Can't validate prim #{where[1]} yet"
    end
  when :recurse
    name = where[1]
    rule = @stage1[name]
    if @recursion < MAX_RECURSE
      @recursion += 1
      r = validate1a(d, rule)
      @recursion -= 1
      r
    else
      fail "Deep recursion into #{name}: #{rule}, not yet implemented"
    end
  else
    @last_message = "Don't know how to validate #{where}"
    false
    # fail where
  end
end

#validate1a(d, where) ⇒ Object

# File 'lib/cddl.rb', line 954

def validate1a(d, where)
  if ann = validate1(d, where)
    here = [d, where]
    if Array === ann
      [here, *ann]
    else
      [here]
    end
  end
end

#validate_diag ⇒ Object

# File 'lib/cddl.rb', line 785

def validate_diag
  [@last_data, @last_rule, @last_message]
end

#validate_forward(d, start, where) ⇒ Object

# File 'lib/cddl.rb', line 816

def validate_forward(d, start, where)
  # warn ["valforw", d, start, where].inspect
  i = 0
  ann = []
  where[1..-1].each { |r|
    t, s, e, _k, v = r # XXX
    if t == :recurse_grpent
      rule = lookup_recurse_grpent(s)
      n, ann2 = validate_linear(d, start+i, rule)
      return [false, ann] unless n
      i += n
      ann.concat(ann2)
    elsif t == :grpchoice
      return [false, ann] unless r[1..-1].any? {|cand|
        n, ann2 = validate_forward(d, start+i, [:foo, *cand])
        if n
          i += n
          ann.concat(ann2)
        end}
    else
      fail r.inspect unless t == :member
      occ = 0
      while ((occ < e) && i != d.size && ((n, ann2 = validate_linear(d, start+i, v)); n))
        i += n
        occ += 1
        ann.concat(ann2)
      end
      if occ < s
        # warn "*** lme #{@last_message.encoding} #{@last_message}"
        # warn "*** #{"\noccur #{occ} < #{s}, not reached at #{i} in array #{d} for #{where}".encoding}"
        @last_message << "\noccur #{occ} < #{s}, not reached at #{i} in array #{d} for #{where}"
        return [false, ann]
      end
    end
  }
  # warn ["valforw>", i].inspect
  [i, ann]
end

#validate_linear(d, start, where) ⇒ Object

returns number of matches or false for breakage

# File 'lib/cddl.rb', line 856

def validate_linear(d, start, where)
  # warn ["vallin", d, start, where].inspect
  fail unless Array === d
  case where[0]
  when :grpent
    # must be inside an array with nested occurrences
    validate_forward(d, start, where)
  else
    (ann = validate1a(d[start], where)) ? [1, ann] : [false, ann]
  end
end

#validate_result(check) ⇒ Object

# File 'lib/cddl.rb', line 809

def validate_result(check)
  check || (
    @last_message << yield
    false
  )
end

#walk(rule, anno = nil, &block) ⇒ Object

# File 'lib/cddl.rb', line 95

def walk(rule, anno = nil, &block)
  r = []
  case rule
  when Array
    r.concat(Array(yield rule, anno))
    case rule[0]
    when :type1, :array, :map
      a = (rule.cbor_annotations rescue nil) if rule.size == 2
      a = a.first if a
      r.concat(rule[1..-1].map{|x| walk(x, a, &block)})
    when :grpchoice
      r.concat(rule[1..-1].map{|x| x.flat_map {|y| walk(y, &block)}})
    when :member
      r << walk(rule[3], &block)
      r << walk(rule[4], &block)
    when :anno
      r << walk(rule[2], &block)
      r << walk(rule[3], &block)
    else
      # p ["LEAF", rule[0]]
    end
  end
  r.compact
end