town envs brainshit

lucidiot's cybrecluster

Well-Known Binary standard avec Kaitai Struct, seconde partie

Lucidiot — Informatique — 2022-01-30
Je n'ai jamais dit qu'on ne se contenterait que de YAML…

On a précédemment bien entamé l'écriture d'une spécification pour le Well-Known Binary « standard » avec Kaitai Struct. Sur les sept types à prendre en charge, on supporte pour l'instant les points, lignes brisées et polygones, et pas les quatre autres. Les quatres types restants sont appelés des entités complexes.

Les entités complexes, dans le jargon géospatial, sont les entités qui contiennent d'autres entités. Dans le WKB standard, ce sont les ensembles de points (multi_point), ensembles de lignes brisées (multi_line_string), ensembles de polygones (multi_polygon) et les collections de géométries (geometry_collection).

Ces ensembles sont définis de façon assez différente des listes de points ou listes de lignes brisées qu'on a vu précédemment pour les lignes brisées et les polygones : au lieu de seulement contenir des coordonnées supplémentaires, les éléments de la liste sont des géométries à part entière. Autrement dit, on répète le boutisme et on répète le type de géométrie, à chaque élément de liste.

Voici par exemple un ensemble de points qu'on définirait en WKT par MULTIPOINT (1 2, 3 4) :

On a trois boutismes, qui peuvent être différents, et deux types : le type 4 correspond à l'ensemble de points et le type 1 correspond à un seul point. En fait, les ensembles sont tous définis comme des versions plus strictes de la collection de géométries, qui peut contenir n'importe quel type de géométrie en même temps. Les ensembles de points, lignes brisées et polygones ne peuvent contenir qu'un seul type de géométrie mais sont définis de la même manière.

On peut aussi observer comment est formatée une collection de géométries vide, c'est-à-dire une GEOMETRYCOLLECTION EMPTY :

Ce n'est rien de plus qu'une collection avec zéro géométries dedans. Cela explique aussi pourquoi un point seul ne peut jamais être EMPTY en WKT, mais une ligne brisée, un anneau linéaire dans un polygone, ou un polygone entier peuvent l'être : il n'y a pas de moyen d'indiquer en WKB qu'un point peut être vide, mais on pourrait déclarer une ligne à zéro points ou un polygone à zéro anneaux.

Gérer les collections de géométries

Pour pouvoir gérer les entités complexes, il va d'abord falloir envelopper toute notre séquence principale dans un nouveau type générique, geometry :

seq:
  - id: geometry
    type: geometry
types:
  geometry:
    seq:
      - id: endianness
        type: u1
      - id: body
        type: geometry_body
  geometry_body:
    seq:
      - id: type
        type: u4
        enum: geometry_type
      - id: data
        type:
          switch-on: type
          cases: ...

On va pouvoir profiter de ce nouveau type pour vite gérer les collections de géométries. On ajoute au cases une nouvelle entrée pour les collections :

cases:
  geometry_type::point: point
  geometry_type::line_string: line_string
  geometry_type::polygon: polygon
  geometry_type::geometry_collection: geometry_collection

Et on peut déclarer un nouveau type pour la collection, qui contiendra un nombre de géométries suivi desdites géométries :

types:
  # ...
  geometry_collection:
    seq:
      - id: count
        type: u4
      - id: geometries
        type: geometry
        repeat: expr
        repeat-expr: count

On gère ainsi immédiatement des collections de n'importe quelle géométrie, y compris des collections de collections de géométries, ou si on est assez fou, des collections de collections de collections de collections de collections de … vous avez compris.

Gérer les ensembles

Pour gérer les ensembles de géométries spécifiques, le principe est similaire que pour les collections. Cependant, nous allons devoir restreindre le type de géométrie autorisé. Il n'y a pas vraiment de moyen élégant de faire ça avec Kaitai, le plus simple sera de définir un nouveau type qui représente des géométries ne pouvant avoir comme type que le point par exemple.

types:
  # ...
  wkb_point:
    seq:
      - id: endianness
        type: u1
      - id: body
        type: wkb_point_body
  wkb_point_body:
    seq:
      - id: type
        type: u4
        enum: geometry_type
      - id: data
        type: point
    meta:
      endian:
        switch-on: _parent.endianness
        cases:
          0: be
          1: le
  multi_point:
    seq:
      - id: count
        type: u4
      - id: points
        type: wkb_point
        repeat: expr
        repeat-expr: count

Je vous laisse imaginer une répétition de ce code pour le multi_line_string et le multi_polygon.

Métamétaprogrammation

La répétition de code est généralement peu recommendable, et si vous avez lu mes précédents articles sur le Well-Known Text, vous savez probablement que j'aime éviter la duplication du code par des méthodes farfelues qui me permettent ensuite de faire des choses encore plus complexes. Une fois le traitement de cette variante du WKB terminé, il y en aura encore d'autres, donc on pourra probablement construire des choses par dessus ce genre de métaprogrammation. Mais dans le contexte actuel, ce n'est pas seulement de la métaprogrammation : Kaitai Struct génère du code, donc le fichier YAML est déjà de la métaprogrammation. Nous faisons donc de la métamétaprogrammation, et bien entendu il y a un XKCD pertinent.

Pour accomplir cette mission, j'avais initialement envisagé de beaucoup souffrir et d'utiliser m4, qu'on a déjà vu auparavant. Ce serait techniquement possible, puisque le YAML est un format texte, mais la gestion de l'indentation serait assez infernale. J'ai donc envisagé un autre langage que j'ai déjà utilisé précédemment pour travailler avec du XML et du JSON, jq. J'ai déjà mentionné cet interpréteur dans des articles précédents ; il est capable d'effectuer des opérations de façon assez performante sur du JSON, un format qui n'est que très rarement performant. Mais si jq génère du JSON, comment va-t-on obtenir du YAML ?

Le format YAML est en fait un sur-ensemble de JSON, c'est-à-dire qu'un fichier JSON est déjà un fichier YAML valide. La question ne se poserait donc même pas. Cependant, on peut si on le souhaite utiliser oq, un programme qui enrobe jq pour y rajouter le support des formats XML et YAML, pour obtenir un fichier YAML plus propre et qui ne ressemble plus à du JSON.

Avec ce nouveau fichier, on pourra donc exécuter soit jq soit oq pour obtenir notre schéma Kaitai Struct :

jq --null-input -f wkb.jq > wkb.ksy
oq --null-input -f wkb.jq -o simpleyaml > wkb.ksy

Définitions de base

On peut commencer notre nouveau script jq avec les définitions assez simples qui ne nécessitent pas de traitement particulier ; les métadonnées, les références à la spécification et l'énumération des types de géométrie. On peut aussi tout de suite inclure notre séquence principale qui contient juste le type geometry.

{
  meta: {
    id: "wkb_std",
    title: "Standard Well-Known Binary",
    license: "AGPL-3.0-or-later",
    xref: {
      iso: "19125-1:2004"
    }
  },
  "doc-ref": [
    "https://www.ogc.org/standards/sfa",
    "http://libgeos.org/specifications/wkb/"
  ],
  seq: [
    {
      id: "geometry",
      type: "geometry"
    }
  ],
  enums: {
    geometry_type: {
      "0": "geometry",
      "1": "point",
      "2": "line_string",
      "3": "polygon",
      "4": "multi_point",
      "5": "multi_line_string",
      "6": "multi_polygon",
      "7": "geometry_collection"
    }
  }
}

Redéfinir les entités simples

On peut commencer par directement définir le point, le type de base :

{
  types: {
    point: {
      seq: [
        {
          id: "x",
          type: "f8"
        },
        {
          id: "y",
          type: "f8"
        }
      ]
    }
  }
}

Pour la ligne brisée et le polygone, on remarquera que les deux utilisent le même système pour gérer la liste d'éléments qu'ils contiennent : un nombre d'éléments, suivi de tous les éléments. On peut donc définir une fonction pour factoriser cette fonctionnalité :

def counted: {
  seq: [
    {
      id: "count",
      type: "u4"
    },
    . + {
      repeat: "expr",
      "repeat-expr": "count"
    }
  ]
};

Cette fonction sera à placer au tout début du fichier, puisqu'elle doit être définie avant qu'on ne construise le document final. On donnera à cette fonction l'ID et le type de l'attribut qui est censé être répété, et elle générera un type entier qui commencera par un nombre d'éléments et répètera l'attribut qu'on a fourni :

{
  types: {
    line_string: ({ id: "points", type: "point" } | counted),
    polygon: ({ id: "rings", type: "line_string" } | counted)
  }
}

Redéfinir les enfants des entités complexes

Les enfants des entités complexes sont comme des géométries, avec leur boutisme et leur type. Je n'avais pas encore défini le type geometry parce que je comptais factoriser les quatre définitions à l'aide d'une seule fonction. La seule différence entre ces quatre définitions sont le contenu qui suit le boutisme et le type. Avec la géométrie, qu'elle soit à la racine du fichier ou dans une collection de géométries, on pourra avoir n'importe quel type. Avec les ensembles de points, lignes brisées ou polygones, on n'aura que des points, lignes brisées ou polygones. Le seul paramètre de notre fonction est donc le type du corps de l'entité.

def wkb_seq: [
  {
    id: "type",
    type: "u4",
    enum: "geometry_type"
  },
  {
    id: "data",
    type: .
  }
];

Cette fonction construit une séquence pour n'importe quel type. On ne va cette fois-ci pas générer un type entier, car la géométrie a besoin de plus que juste une séquence et ce sera donc plus simple à gérer comme ça. On peut utiliser cette fonction, en combinaison avec la précédente, pour définir les enfants des entités complexes :

{
  types: {
    wkb_point: { seq: ("point" | wkb_seq) }
    wkb_line_string: { seq: ("line_string" | wkb_seq) }
    wkb_polygon: { seq: ("polygon" | wkb_seq) }
  }
}

Redéfinir les entités complexes

Les entités complexes vont contenir une liste des géométries que nous venons de redéfinir, donc on peut déjà utiliser counted pour les définir :

{
  types: {
    multi_point: ({ id: "points", type: "wkb_point" } | counted),
    multi_line_string: ({ id: "line_strings", type: "wkb_line_string" } | counted),
    multi_polygon: ({ id: "polygons", type: "wkb_polygon" } | counted),
    geometry_collection: ({ id: "geometries", type: "geometry" } | counted)
  }
}

Il ne nous reste plus qu'à gérer le boutisme pour pouvoir les définir entièrement, et aussi définir la géométrie elle-même. Pour gérer le boutisme, on avait à chaque fois entouré le type par un autre type qui contient la valeur de l'attribut de boutisme, et permet au type d'origine de voir son boutisme être influencé par cette valeur. On peut donc avoir une fonction qui reçoit un type entier, l'entoure par l'attribut endianness, et modifie le type pour influencer son boutisme :

def endianize: {
  seq: [
    {
      id: "endianness",
      type: "u1"
    },
    {
      id: "body",
      type: "body"
    }
  ],
  types: {
    "body": (. + {
      meta: {
        endian: {
          "switch-on": "_parent.endianness",
          cases: {
            "0": "be",
            "1": "le"
          }
        }
      }
    })
  }
};

On peut utiliser ça pour redéfinir les enfants des entités complexes pour qu'ils gèrent le boutisme :

{
  types: {
    wkb_point: ({ seq: ("point" | wkb_seq) } | endianize),
    wkb_line_string: ({ seq: ("line_string" | wkb_seq) } | endianize),
    wkb_polygon: ({ seq: ("polygon" | wkb_seq) } | endianize)
  }
}

Redéfinir la géométrie

On peut désormais encapsuler tous ces types dans un seul type geometry. Ce type utilisera endianize pour le boutisme, et utilisera wkb_seq pour construire sa séquence ; le type ne sera cette fois pas seulement une chaîne de caractères, mais le block switch-on que l'on a utilisé pour relier l'enumération aux différents types qu'on a défini.

{
  geometry: ({
    seq: ({
      "switch-on": "type",
      cases: {
        "geometry_type::point": "point",
        "geometry_type::line_string": "line_string",
        "geometry_type::polygon": "polygon",
        "geometry_type::multi_point": "multi_point",
        "geometry_type::multi_line_string": "multi_line_string",
        "geometry_type::multi_polygon": "multi_polygon",
        "geometry_type::geometry_collection": "geometry_collection"
      }
    } | wkb_seq),
    types: {
      # Tous les types définis précédemment
    }
  } | endianize)
}

Conclusion

Nous avons maintenant pu gérer tous les types d'entités du Well-Known Binary standard avec Kaitai Struct, et avons factorisé le schéma de sorte à le rendre parfaitement illisible mais surtout à le rendre plus extensible pour gérer les deux prochaines variantes. Voici le script final :

#!/usr/bin/jq
# Generates a Kaitai Struct-compatible JSON structure to parse
# the standard Well-Known Binary.
# Usage: oq -n -o simpleyaml -f wkb.jq  wkb.ksy

def endianize: {
  seq: [
    {
      id: "endianness",
      type: "u1"
    },
    {
      id: "body",
      type: "body"
    }
  ],
  types: {
    "body": (. + {
      meta: {
        endian: {
          "switch-on": "_parent.endianness",
          cases: {
            "0": "be",
            "1": "le"
          }
        }
      }
    })
  }
};

def counted: {
  seq: [
    {
      id: "count",
      type: "u4"
    },
    . + {
      repeat: "expr",
      "repeat-expr": "count"
    }
  ]
};

def wkb_seq: [
  {
    id: "type",
    type: "u4",
    enum: "geometry_type"
  },
  {
    id: "data",
    type: .
  }
];

{
  meta: {
    id: "wkb_std",
    title: "Standard Well-Known Binary",
    license: "AGPL-3.0-or-later",
    xref: {
      iso: "19125-1:2004"
    }
  },
  "doc-ref": [
    "https://www.ogc.org/standards/sfa",
    "http://libgeos.org/specifications/wkb/"
  ],
  seq: [
    {
      id: "geometry",
      type: "geometry"
    }
  ],
  enums: {
    geometry_type: {
      "0": "geometry",
      "1": "point",
      "2": "line_string",
      "3": "polygon",
      "4": "multi_point",
      "5": "multi_line_string",
      "6": "multi_polygon",
      "7": "geometry_collection"
    }
  },
  types: {
    geometry: ({
      seq: ({
        "switch-on": "type",
        cases: {
          "geometry_type::point": "point",
          "geometry_type::line_string": "line_string",
          "geometry_type::polygon": "polygon",
          "geometry_type::multi_point": "multi_point",
          "geometry_type::multi_line_string": "multi_line_string",
          "geometry_type::multi_polygon": "multi_polygon",
          "geometry_type::geometry_collection": "geometry_collection"
        }
      } | wkb_seq),
      types: {
        point: {
          seq: [
            {
              id: "x",
              type: "f8"
            },
            {
              id: "y",
              type: "f8"
            }
          ]
        },
        line_string: ({ id: "points", type: "point" } | counted),
        polygon: ({ id: "rings", type: "line_string" } | counted),
        wkb_point: ({ seq: ("point" | wkb_seq) } | endianize),
        wkb_line_string: ({ seq: ("line_string" | wkb_seq) } | endianize),
        wkb_polygon: ({ seq: ("polygon" | wkb_seq) } | endianize),
        multi_point: ({ id: "points", type: "wkb_point" } | counted),
        multi_line_string: ({ id: "line_strings", type: "wkb_line_string" } | counted),
        multi_polygon: ({ id: "polygons", type: "wkb_polygon" } | counted),
        geometry_collection: ({ id: "geometries", type: "geometry" } | counted)
      }
    } | endianize)
  }
}

La prochaine fois, nous affronterons le WKB ISO, qui introduira la gestion de dimensions multiples ainsi que de nouveaux types de géométries. On va s'amuser à rajouter encore plus de fonctions, de parenthèses et d'accolades…

Commentaires

Il n'y a pour l'instant aucun commentaire. Soyez le premier !