146 lines
11 KiB
Markdown
146 lines
11 KiB
Markdown
# 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)
| |
1. 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).
| |
2. 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.
| |
3. Tipos base 0 a 5: ARR, OBJ, UINT, INT, FLT, BOL con esos valores (TSN_SBL_BASE_TYPE_*), el NodeBase compara contra ellos.
| |
4. 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.
| |
5. 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).
| |
6. El tipo va en los 5 primeros bits (TSN_SBL_BIT_MASK_TYPE), hasta 32 tipos.
| |
7. 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[](BSFLPointerQuery) |
| |
| 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 <TKey>. 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 <T>. 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 <T>. 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 <TKey>. El string crudo (sin unescape) desde m_raw |
| |
| GetRawAsUArr | Template <TKey>. 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
| |
| |
```mql5
| |
//--- 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):
| |
| |
1. 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).
| |
2. 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.
| |
3. 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.
| |
4. 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.
| |
5. 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.
|