Especificaciones

Aqui documento que ha de cumplir TCtx (el parser) y TOut (el nodo) para poder heredar limpio de CNodeSFLBase, dado que esta struct es un template y asume que hay varias funciones, arrays, etc definidas... si no se definen dara errores de compilacion.

La idea es: CNodeSFLBase llama a m_ctx.* y a TOut::*, estas son las funciones que se esperan y que se supone que deben hacer.

Generales

Las key trabajan sobre indices en la cinta ("fase 1"), no materializan el string. Las key son string, y en cada lenguaje puede haber varios tipos de string, eso lo resuelve GetStrAsStr. Pero como las key rara vez tienen escapes no deben pagar ese costo, por eso se toma lo comun: retornar el indice en tape.
ToString, ToInt, ToUInt, ToDouble no estan en el NodeBase. ToString es algo general (switch sobre el tipo, si es string se resuelve, si no se castea) y no se cuantos tipos de string tendra cada lenguaje, por eso junto a ToInt\ToUInt\ToDouble los deja el nodo hijo, para no forzar un patron.
Todo lo que implica devolver un string key, si falla retorna NULL.
El hash de key es FNV1A64 sobre los bytes ya desescapados (UTF-8). El hash que calcula el parser (MakeHash o el propio) debe dar el mismo valor que FNV1A_64_AsM_Str sobre el string de busqueda, si no operator[], Get y los pointers nunca encontraran la key.

Obligatorio (layout en la cinta)

ARR y OBJ: header de 1 slot [tipo|count|step] + 1 slot extra (TSN_SBL_SLOT_ARR_SIZE\TSN_SBL_SLOT_OBJ_SIZE = 2). El segundo slot en OBJ es del JIT [intentos(63 bits)|is_jit<<63]. En ARR esta reservado, el parser hijo puede usarlo como quiera (pila temporal, etc).
UINT, INT, FLT: header + 1 slot con el valor de 64 bits (2 slots). BOOL: 1 slot, el valor va en TSN_SBL_BIT_START_BOOL.
Tipos base 0 a 5: ARR, OBJ, UINT, INT, FLT, BOL con esos valores (TSN_SBL_BASE_TYPE_*), el NodeBase compara contra ellos.
KEY ocupa TSN_SBL_KEYSLOT_SIZE slots (hoy 2): [key][hash], el hash esta en TSN_SBL_KEY_OFF_HASH. El bit 5 de la key es TSN_SBL_KEY_FLAG_HASH (1 = el hash ya fue calculado), no usarlo para otra cosa en keys. Los iteradores y NodeHashing saltan la key con TSN_SBL_KEYSLOT_SIZE.
El STRING base es de 1 slot. Los demas tipos de string (plain, multilinea, etc) son extensiones y pueden usar los slots que quieran con su propio layout (TSN_SBL_BASE_TYPE_STR = 6 es solo una sugerencia que usan el DOM y el Query, el NodeBase no lo usa).
El tipo va en los 5 primeros bits (TSN_SBL_BIT_MASK_TYPE), hasta 32 tipos.
En OBJ el valor sigue a la key, el siguiente par empieza en key + KEYSLOT + GetStep(valor).

Lo que debe tener TCtx

Heredar de CBaseStructuredLan ya da: m_cinta, m_raw, m_len, m_cinta_pos, m_tables, m_tables_size, m_pfh, m_max_att, m_jit_enabled, PerfectHashAcces, PerfectHashComputeHashIndex y FindNodePos.

Name	Que se supone que debe de hacer
s_dtype_to_str	static const string[] indexado por el valor del tipo. Un string vacio significa "tipo no valido" (lo usa IsValidDataType), TypeToMqlStr retorna el valor directo
s_unescape_table	static const uchar[256] que usa CBSFLUnescape (MakeString, MakeUArray, MakeHash) con TBackend. El nombre debe ser exactamente este
CalcRegType	Mapea el nombre de archivo a un tipo de extension (AssingFile lo llama, debe retornar TSN_SLF_EXT_TYPE_CACHE_FILE para el cache compilado)

Lo que debe tener TOut (el nodo)

Name	Que se supone que debe de hacer
EMPTY_NODE	static const TOut, nodo invalido (ctx NULL, idx -1) que se retorna en cualquier fallo
Constructor ()	Nodo invalido: ctx NULL, idx -1, end -1, node_pos -1
Constructor (ctx, idx)	Calcula end = idx + GetStep(idx) y node_pos con NODEBASEF_RES_BASE. Lo usan operator[], Get, At, AtObj, AtHomegeneo, MoveNextPositions
Constructor (ctx, idx, end)	Solo calcula node_pos (NODEBASEF_RES_BASE). Lo usan los iteradores en Val()
Constructor (ctx, idx, end, node_pos)	Clonacion, no resuelve nada. Lo usan GetAs y operator
OnMute	static void OnMute(CNodeSFLBase& node), se llama despues de mover m_idx (MoveToNextToken, MoveNextPositionsThis). Debe recalcular node_pos (RecalcNodePos) y m_end. Aqui es donde un lenguaje con refs\alias resuelve el salto

Funciones de TCtx que llama el nodo

Todas reciben posiciones en la cinta (cur, end). Las que dicen "cur apunta a la key" es la primera key del objeto (header + TSN_SBL_SLOT_OBJ_SIZE), no al header.

Name	Que se supone que debe de hacer
GetStep	Dado idx retorna cuantos slots ocupa el nodo completo (hijos incluidos). ARR\OBJ lo sacan del header (step), UINT\INT\FLT 2, BOOL\STR\NULL 1, KEY TSN_SBL_KEYSLOT_SIZE. Se llama sobre valores, nunca sobre la key en iteracion
GetStepPure	Slots del token propio sin recorrer hijos (ARR\OBJ = solo el header). Lo usa MoveToNextToken y los ExistInArray para navegar token a token
NodeAt	Dado un cur (primer elemento del arr) y un index, iterar saltando nodos con GetStep index veces y retornar cur donde quedo. No valida rango
NodeObjAtSlow	Dado un cur (apuntando a la 1era key) y un index, iterar index veces (key + valor) y retornar cur apuntando a esa key. No suma KEYSLOT, eso lo hace el NodeBase
NodeFindByHashFvn1A64	Dado un hash kh, un cur (1era key) y un end, recorrer los pares y retornar la posicion de la KEY cuyo hash es igual, o -1. El hash de cada key se calcula perezosamente: si TSN_SBL_KEY_HAS_ISN_HASH calcula, guarda en cur+KEY_OFF_HASH y marca TSN_SBL_KEY_FLAG_HASH. Si no se puede calcular (string invalido) guardar kh+1 para que nunca coincida. El NodeBase suma TSN_SBL_KEYSLOT_SIZE para ir al valor
NodeKeyToPositionSlow	Igual que el anterior pero retorna el indice ordinal de la key (0, 1, 2...) en el objeto, o -1
NodeGetKeys	Recibe cur = header del objeto (aqui si el header, el suma TSN_SBL_SLOT_OBJ_SIZE el mismo) y un end. Debe hacer ArrayResize de keys[] al numero de keys, llenarlo y retornar ese numero. Si una key falla retornar NULL en esa posicion
NodeHashing	Construye el perfect hash del objeto en curr (header). Parametros (curr, obj_count, bend, table_pos&). Pasos: BASESPARSERSLAN_START_NODE_HASH(table_pos, curr) reserva\reutiliza la entrada en m_tables; llenar pos_arr[] con la posicion de cada key; obtener (o calcular y cachear) el hash de cada key; m_pfh.MaxValSeed(m_max_att++), InitAlg(obj_count, 0.70, 4); resize de pos_index y key_hash (key_hash a 0); sizes = BSFL_T_PACK(m_buckets_size_last, m_final_table_size_last); RunWValue. Si algo falla: cinta[curr+1] = TSN_SBL_BIT_JIT_INV_VAL y m_tables_size-- (para no volver a intentar)
GetStrAsStr	Template . Recibe idx (slot del string o de la key) y string& res, retorna bool. Helper que convierte el nodo a un string valido en el lenguaje resolviendo escapes. No valida que sea string. TKey (uchar para key, ushort para string) solo se usa para calcular el ancho del len
GetStrAsUArr	Igual pero a uchar[] en UTF-8 desde la posicion pos. Retorna cantidad de bytes, -1 si falla
ToArray	Template . Dado cur (primer elemento) y end, volcar el arr castenando a T. El NodeBase ya hizo ArrayResize con count, el tipo del primer elemento define como castear (se asume homogeneo)
ExistInArray	Template . Dado cur, valor T, flags (mascara 1<<tipo de los tipos a revisar) y end, revisa si val esta en el arr castenando cada elemento a T. Los tipos que no estan en flags se saltan
ExistInArrayHomogeneo	Lo mismo pero asumiendo el tipo del primer elemento para todos: el step se calcula una vez (o es fijo, 1 o 2) y se avanza directo, sin branchs extras ni GetStep
SerializeToDom	(CDomNodeBase* root, CDomNodeManager* manager, cur, end). cur es el header de un ARR\OBJ. Debe volcar el subarbol al DOM (root.NewObj\NewArr con el count y luego los hijos). Retorna bool. Lo usa ToDom

Opcionales

El NodeBase no las llama, son las que el nodo hijo del json usa para implementar ToString y demas. Si el lenguaje las necesita mejor mantener los mismos nombres:

Name	Que se supone que debe de hacer
GetRawAsStr	Template . El string crudo (sin unescape) desde m_raw
GetRawAsUArr	Template . Igual pero a uchar[]
GetRoot	Retorna el nodo raiz (idx 0, end = GetStep(0)), EMPTY_NODE si la cinta esta vacia

Ejemplo masomenos de como se haria

  //--- Step
  __forceinline int  GetStep(const int idx) const;
  __forceinline int  GetStepPure(const int idx) const;

  //--- Node
  void               NodeHashing(int curr, const int obj_count, const int bend, int& table_pos);
  bool               SerializeToDom(CDomNodeBase* root, CDomNodeManager* manager, int cur, const int end);

  //--- Strings\Keys
  template<typename TKey>
  __forceinline bool GetStrAsStr(int idx, string &res) const;
  template<typename TKey>
  __forceinline int  GetStrAsUArr(int idx, uchar &res[], int pos = 0) const;

  //--- Funciones para node
  template <typename T>
  void               ToArray(int cur, T& out_arr[], const int end) const;
  template <typename T>
  bool               ExistInArray(int cur, const T val, const uint flags, const int end) const;
  template <typename T>
  bool               ExistInArrayHomogeneo(int cur, const T val, const int end) const;
  __forceinline int  NodeAt(int cur, const int index) const;
  int                NodeFindByHashFvn1A64(const ulong kh, int cur, const int end);
  __forceinline int  NodeObjAtSlow(int cur, const int index) const;
  int                NodeKeyToPositionSlow(const ulong kh, int cur, const int end);
  int                NodeGetKeys(int cur, string &keys[], const int end) const;

  //--- Tablas
  static const string s_dtype_to_str[];
  static const uchar  s_unescape_table[256];

JIT

El JIT funciona asi (esta implementado en CNodeSFLBase::operator[] y Get):

El slot 2 del OBJ (header + 1) es el contador de intentos. Al parsear arranca en TSN_SBL_BIT_JIT_INITIAL_V (1), o en TSN_SBL_BIT_JIT_INV_VAL si las opciones desactivan el JIT (m_jit_enabled).
En cada acceso por key el contador se reduce en 1:

Si llega a 0 (primer acceso): si el objeto tiene menos de TSN_NODEBASEREAD_MIN_JIT_VALUES_TO_HASH (4) valores no vale la pena, se pone TSN_SBL_BIT_JIT_INV_VAL. De lo contrario se pone TSN_NODEBASEREAD_MIN_JIT_ATTEMPS_TO_PHASH (5).
Si llega a 1 (se acabaron los intentos): se llama a NodeHashing.

Mientras no hay tabla (m_node_pos == -1) se busca lineal con NodeFindByHashFvn1A64, y en cada key visitada el hash se calcula y se guarda en la cinta (lazy), asi cuando NodeHashing corre ya hay muchos hasheados.
Si NodeHashing funciona la tabla queda en m_tables y el nodo usa PerfectHashAcces (m_node_pos != -1). Cualquier otro nodo la encuentra con FindNodePos (busca por start) al construirse.
Si falla (keys duplicadas, el pfh no encontro seeds) se pone TSN_SBL_BIT_JIT_INV_VAL y no se vuelve a intentar, se sigue con busqueda lineal. NodeHashing debe dejar m_tables_size como estaba antes de entrar.

La idea es primero una etapa perezosa, ir construyendo los hashes poco a poco, y solo si el objeto se consulta muchas veces terminar de construir la tabla.

11 KiB RawPermalinkBlameHistory