Commits

Dmitry Grebeniuk  committed f5cc996

shit again

  • Participants
  • Parent commits 69b7c64

Comments (0)

Files changed (1)

File iteratees.ml

 ;
 
 
-module Deque_chunks
+module Deque_stream
  =
   struct
 
 
 
+на первом шаге it_subseq_step должен выдавать None для "не нашли"
+и Some (то, что дают итераты, только в option) для "есть значение!"
+или "? хочу ещё данных"
+!
+
+
 value break_subsequence
- : (S.t 'el -> int -> IO.m (iteratee 'el 'a * stream 'el)) ->
+ : (S.t 'el -> int -> option (iteratee 'el 'a * stream 'el)) ->
    iteratee 'el 'b ->
    iteratee 'el (option 'a * iteratee 'el 'b)
  = fun it_subseq_step it_proc_until ->
           последнего чанка.
           копирование будет однократным, так как из хвоста чанки не берутся,
           а только добавляются туда.
-
-break_subsequence : берёт очередь
-    если it_proc_until кончил -- возвращаем его и склеенную очередь
-    иначе -- loop_q с очередью
-
-loop_q : берёт очередь
-    если очередь:
-    - пустая -- step0
-    - непустая -- берём голову, вызываем loop_index
-
-step0 :
-    запрашиваем чанк, loop_index с первым чанком, смещением=0 и пустым хвостом
-
-loop_index : берёт первый чанк, начальное смещение, хвост очереди
-    пытаемся последовательно по всем смещениям применить it_subseq_step:
-    - когда дошли до конца чанка,
-      - Кормить
-      - идём дальше: break_subsequence по хвосту (там же оно выйдет,
-        если итерат кончил)
-      (проверка на конец должна быть в начале, так как step1 может дать ofs=len)
-    - пока ошибка, идём по чанку к следующему смещению.
-    - когда не ошибка, а "хочу ещё" от it_subseq_step --
-      - Кормить
-        - если после кормления есть результат от it_proc_until -- возвращаем
-          его, склеиваем
-          остаток после кормления и хвост очереди, возвращаем всё
-        - если нет результата --
-          - очередь формируем доклеиванием спереди текущего смещения и текущего
-            чанка к хвосту очереди
-          - очередь и продолжение от it_subseq_step передаём в step1
-    - когда результат от it_subseq_step -- Кормить, возвращаем его и результат
-      от it_subseq_step (если кормёжка оставила кусок чанка, игнорируем)
-    где:
-    Кормить =
-      кормим it_proc_until куском текущего чанка от начального до текущего
-      смещения, имеющихся в значениях loop_index
-
-step1 : берёт продолжение it_subseq_step и очередь
-тут: очередь непуста
-    запрашиваем чанк
-    1. доклеиваем в зад очереди (должно скопировать предыдущий чанк)
-    2. пытаемся его применить к продолжению it_subseq_step
+должна уметь:
+snoc : stream -> q
+  добавить чанк в конец с копированием предыдущего чанка
+    (копировать только кусок от ofs до len)
+concat : q -> chunk
+  склеить очередь (копирование)
+split_at_head : q -> option (chunk * q)  (* None | Some (hd, tl) *)
+
+
+let rec break_subsequence q it_proc_until =
+  match it_proc_until with
+  [ IE_done _ | IE_cont (Some _) _ ->
+      (* если it_proc_until кончил -- возвращаем его и склеенную очередь *)
+      ie_doneM (None, it_proc_until) (Deque_stream.concat q)
+
+
+> [Monday, 30 July 2012 14:13:34 Дмитрий Гребенюк] Представим расклад:
+тестирующий итерат запросил чанки [1;2] ; [3;4], пока не нашёл нужную
+последовательность, запрашивает ещё, получает EOF, выдаёт ошибку
+(так как не нашёл нужного).  Что делаем: идём по смещениям дальше:
+обрабатываем [2]; [3;4]; EOF тестирующим итератом, тоже ошибка.
+Дальше надо продолжить обрабатывать [3;4]; EOF, но надо скормить чанк [1;2]
+обрабатывающему итерату.  И вот, он кончил, ему больше не надо данных.
+Чо делать?  Возвращать [3;4]; EOF как остаток.  И вот тут -- снова те же яйца.
+Возвратить можно либо [3;4], либо EOF, в качестве остатка необработанных
+данных.  Возвратим [3;4] -- нарушим закон "итерат, получающий EOF, должен
+возвратить значение либо ошибку", так как за этим итератом может быть
+"прибинжен" итерат, который возьмёт [3;4], ему будет мало, и он захочет ещё
+данных, тогда как вся комбинация обязана возвратить значение либо ошибку,
+но не "хочу ещё данных".  Если же вернём EOF, то проебём [3;4], и прибинженный
+итерат их не получит.
+
+
+
+
+  | IE_cont None k_proc ->
+      (* иначе -- loop_q с очередью *)
+      loop_q q k_proc
+  ]
+
+and loop_q q k_proc =
+  match Deque_stream.split_at_head q with
+  [ None -> step0 k_proc
+  | Some (first_ofs, first_chunk) -> вызываем loop_index
+  ]
+
+and step0 k_proc =
+  (* запрашиваем чанк, loop_index с первым чанком,
+     смещением=0 и пустым хвостом.  вызывается из loop_q. *)
+  ie_cont & fun
+  [ Chunk c -> loop_index c 0 k_proc ~qtail:Deque_stream.empty
+  | (EOF _ ) as s -> ie_doneM (None, ie_cont k_proc) s
+  ]
+
+and loop_index first_chunk first_ofs k_proc ~qtail =
+
+  (* Кормить = *)
+  let feed_first_chunk ~cur_ofs:ofs k_proc =
+    (* кормим it_proc_until куском текущего чанка от начального до текущего
+       смещения, имеющихся в значениях loop_index *)
+    .
+
+  (* пытаемся последовательно по всем смещениям применить it_subseq_step: *)
+  let first_len = S.length first_chunk in
+  let rec loop_ofs ofs =
+    let () = assert (ofs <= first_len) in
+    (* проверка на конец должна быть в начале, так как step1 может
+       дать ofs=len *)
+    if ofs = first_len
+    then
+      (* - когда дошли до конца чанка, *)
+      (*   - Кормить *)
+      feed_first_chunk ~cur_ofs:ofs k_proc >>% fun (it_proc, _s_proc) ->
+      (*   - идём дальше: break_subsequence по хвосту (там же оно выйдет,
+             если итерат кончил), и остаток потока тут не важен *)
+      break_subsequence qtail it_proc
+    else
+      match it_subseq_step first_chunk first_ofs with
+      [ None ->
+          (* - пока ошибка, идём по чанку к следующему смещению. *)
+          loop_index first_chunk (first_ofs + 1) k_proc ~qtail
+      | Some (sq_it, sq_left) ->
+          match sq_it with
+          [ IE_done _ ->
+             (* - когда результат от it_subseq_step -- *)
+             (*   - Кормить *)
+             feed_first_chunk ~cur_ofs:ofs k_proc >>% fun (it_proc, _s_proc) ->
+             (*   - возвращаем его и результат от it_subseq_step (если
+                     кормёжка оставила кусок чанка -- игнорируем)
+             *)
+             .
+          | IE_cont (Some _) _ -> assert False
+              (* так как в первом шаге итерат должен вернуть None
+                 на случай типа-ошибки *)
+          | IE_cont None k_sub -> ...
+              (* - когда не ошибка, а "хочу ещё" от it_subseq_step -- *)
+              (*   - Кормить *)
+              feed_first_chunk ~cur_ofs:ofs k_proc >>% fun (it_proc, s_proc) ->
+              match it_proc with
+              [ IE_done _ | IE_cont (Some _) _ ->
+                  (* - если после кормления есть результат от it_proc_until --
+                       возвращаем его, склеиваем остаток после кормления и
+                       хвост очереди, возвращаем всё *)
+                  .
+              | IE_cont None k_proc ->
+                  (* - если нет результата -- *)
+                  (*   - очередь формируем доклеиванием спереди текущего
+                         смещения и текущего чанка к хвосту очереди *)
+                  .
+                  (*   - очередь и продолжение от it_subseq_step передаём в
+                         step1 *)
+                  .
+              ]  (* match it_proc *)
+          ]  (* match sq_it *)
+      ]  (* match it_subseq_step option *)
+  in
+    loop first_ofs
+
+(* запросить ещё чанки для тестирования их продолжением k_sub *)
+and step1 k_sub k_proc q =
+  (* тут: очередь непуста *)
+  let () = assert (not (Deque_stream.is_empty q)) in
+  (* запрашиваем чанк *)
+  ie_cont & fun s ->
+  match s with
+  [ EOF _ ->
+      доклеить s в зад очереди
+
+      дать s в k_sub, посмотреть на результат.
+
+       - если ошибка -- loop_index со следующего смещения в первом чанке
+         очереди (может дать ofs=len)
+       - если результат -- возвращаем Some res, ie_cont k_proc, EOF _
+
+  | Chunk c ->
+      (* 1. доклеиваем в зад очереди (должно скопировать предыдущий чанк) *)
+      let q = Deque_stream.snoc_chunk c 0 q in
+      (* 2. пытаемся его применить к продолжению it_subseq_step *)
+      k_sub s 
        - если ошибка -- loop_index со следующего смещения в первом чанке
          очереди (может дать ofs=len)
        - если результат -- возвращаем остаток потока, нетронутый it_subseq_step,