(** Structure classification. *)
(* Memory info command for virtual domains.
   (C) Copyright 2008 Richard W.M. Jones, Red Hat Inc.
   http://libvirt.org/

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 *)

(**
   {2 How it works}

   There's no getting around it, this is complicated.

   {!Pahole_parser} has parsed in a limited set of structures from
   each available kernel.  We now aim to take a holistic view of
   a structure as it changed over time, though different kernel
   versions and also on different architectures.

   {3 Shape fields and content fields}

   A structure is a list of fields.

   Fields fall into two classifications, as far as we are interested:

   (i) 'Shape' fields define the relationship between different
   structures.  Shape fields are all pointers to other structures
   that we care about.   They have type {!Pahole_parser.FStructPointer}
   and {!Pahole_parser.FListHeadPointer}.

   (ii) 'Content' fields are fields in a structure that contain
   some data, like ints and strings.  (In the current implementation,
   it's anything left which isn't a shape field).

   So we can easily take a structure and place its fields into two
   buckets.  For example, with [task_struct] it might be:

   [task_struct] shape fields:
   - [tasks'next]  (the linked list of tasks)
   - [tasks'prev]
   - [parent]      (points to the parent task)

   [task_struct] content fields:
   - [pid]  (process ID)
   - [comm] (task name)
   - etc. etc.

   {3 Shape fields and iterator functions}

   For each kernel/structure we can build a list of shape fields, but
   in fact in many kernels they will be the same, so we also
   performing a {i sharing} operation to minimize the number of
   variations.

   We also write (by hand) iterator functions.  These iterator
   functions are matched to the corresponding shape field structure,
   by setting up some prerequisites that the function needs, then
   matching on those prerequisites with the available shape
   field structures.

   {3 Content fields and printing functions}

   The same (minimization & matching) applies to hand-written printing
   functions over content field structures.

   {3 Generated parsing functions}

   A third form of minimization is required to find kernel
   structures which happen to be similar - ie. all the fields
   happen to be in the same place, with the same wordsize and
   endianness.

   We can then generate a minimal set of parsing functions which
   map the binary data from the kernel image into shape and
   content field structures.

   {3 Generated loading code}

   Finally, we generate recursive loading code which recurses over
   structures into order to load the kernel memory and invoke the
   correct parsers on it, ensuring that when the program runs, all
   known kernel structures are recursively reached and loaded in.
*)

(** {2 Field classification} *)

type f_class = ShapeField | ContentField

val classify_field : string list -> Pahole_parser.f_type -> f_class
  (** [classify_field names field] classifies a field as either
      a shape field or a content field.  [names] is a list of
      all kernel structures that we care about. *)

(** {2 Minimization of shape field structures and content field structures} *)

type shape_field_struct = {
  sf_i : int;				(** Unique number. *)
  sf_name : string;			(** Structure name in output. *)
  sf_fields : Pahole_parser.field list;	(** Shape fields. *)
}
    (** The type of a shape field structure. *)

and content_field_struct = {
  cf_i : int;				(** Unique number. *)
  cf_name : string;			(** Structure name in output. *)
  cf_fields : Pahole_parser.field list; (** Content fields. *)
}
    (** The type of a content field structure. *)

type sfhash = (string, shape_field_struct) Hashtbl.t
    (** Hash of kernel version to the shape field structure. *)

val minimize_shape_field_structs :
  string -> string list ->
  (Pahole_parser.info * Pahole_parser.structure) list ->
  shape_field_struct list * sfhash
    (** [minimize_shape_field_structs struct_name names kernels] returns
	a minimized list of shape field structures
	(a hash table of kernel version to {!shape_field_struct}).

	[struct_name] is the name of the structure.

	[names] is the list of interesting kernel structures. *)

type cfhash = (string, content_field_struct) Hashtbl.t
    (** Hash of kernel version to the content field structure. *)

val minimize_content_field_structs :
  string -> string list ->
  (Pahole_parser.info * Pahole_parser.structure) list ->
  content_field_struct list * cfhash
    (** [minimize_content_field_structs struct_name names kernels] returns
	a minimized list of content field structures
	(a hash table of kernel version to {!content_field_struct}).

	[struct_name] is the name of the structure.

	[names] is the list of interesting kernel structures. *)

(** {2 Minimization of parsers} *)

type parser_ (* parser is a reserved word *) = {
  pa_i : int;			        (** Unique number. *)
  pa_name : string;			(** Parser function name in output. *)
  (* The input to the parser: *)
  pa_endian : Bitstring.endian;	        (** Default field endianness. *)
  pa_fields : Pahole_parser.field list; (** All fields. *)
  (* The output of the parser: *)
  pa_shape_field_struct : shape_field_struct;
  pa_content_field_struct : content_field_struct;
}
    (** The type of a parser. *)

type pahash = (string, parser_) Hashtbl.t
    (** Hash of the kernel version to the parser. *)

val minimize_parsers :
  string ->
  (Pahole_parser.info * Pahole_parser.structure) list ->
  sfhash -> cfhash ->
  parser_ list * pahash
    (** [minimize_parsers struct_name kernels sfhash cfhash] returns
	a minimized list of parsers (a hash table of kernel version
	to {!parser_}).

	[sfhash] and [cfhash] are the kernel version -> shape/content
	field struct hashes returned by a previous call to
	{!minimize_shape_field_structs} and {!minimize_content_field_structs}
	respectively. *)