{-# LANGUAGE BangPatterns        #-}
{-# LANGUAGE FlexibleContexts    #-}
{-# LANGUAGE FlexibleInstances   #-}
{-# LANGUAGE ScopedTypeVariables #-}

module HaskellWorks.Data.BalancedParens.Internal.Broadword.Word64
  ( findUnmatchedClose
  ) where

import Data.Word
import HaskellWorks.Data.Bits.BitWise
import HaskellWorks.Data.Bits.Broadword.Word64
import HaskellWorks.Data.Bits.Word64

-- | Find the position of the first unmatch parenthesis within a word.
--
-- See [Broadword Implementation of Parenthesis Queries](https://arxiv.org/pdf/1301.5468.pdf), Sebastiano Vigna, 2013
findUnmatchedClose :: Word64 -> Word64
findUnmatchedClose :: Word64 -> Word64
findUnmatchedClose Word64
x =
  let !b00 :: Word64
b00 = Word64
x forall a. Num a => a -> a -> a
- ((Word64
x forall a. BitWise a => a -> a -> a
.&. Word64
0xaaaaaaaaaaaaaaaa) forall a. Shift a => a -> Word64 -> a
.>. Word64
1)                                               in
  let !b01 :: Word64
b01 = (Word64
b00 forall a. BitWise a => a -> a -> a
.&. Word64
0x3333333333333333) forall a. Num a => a -> a -> a
+ ((Word64
b00 forall a. Shift a => a -> Word64 -> a
.>. Word64
2) forall a. BitWise a => a -> a -> a
.&. Word64
0x3333333333333333)                  in
  let !b02 :: Word64
b02 = (Word64
b01 forall a. Num a => a -> a -> a
+ (Word64
b01 forall a. Shift a => a -> Word64 -> a
.>. Word64
4)) forall a. BitWise a => a -> a -> a
.&. Word64
0x0f0f0f0f0f0f0f0f                                           in
  let !b03 :: Word64
b03 = (Word64
b02 forall a. Num a => a -> a -> a
* Word64
0x0101010101010101) forall a. Shift a => a -> Word64 -> a
.<. Word64
1                                                     in
  let !b04 :: Word64
b04 = Int -> Word64 -> Word64 -> Word64
kBitDiffUnsafe Int
8 (Int -> Word64
h Int
8 forall a. BitWise a => a -> a -> a
.|. Word64
0x4038302820181008) Word64
b03                                    in
  let !u00 :: Word64
u00 = (((((Word64
b04 forall a. BitWise a => a -> a -> a
.|. Int -> Word64
h Int
8) forall a. Num a => a -> a -> a
- Int -> Word64
l Int
8) forall a. Shift a => a -> Word64 -> a
.>. Word64
7) forall a. BitWise a => a -> a -> a
.&. Int -> Word64
l Int
8) forall a. BitWise a => a -> a -> a
.|. Int -> Word64
h Int
8) forall a. Num a => a -> a -> a
- Int -> Word64
l Int
8                              in
  let !z00 :: Word64
z00 =                         ((Int -> Word64
h Int
8 forall a. Shift a => a -> Word64 -> a
.>. Word64
1) forall a. BitWise a => a -> a -> a
.|. (Int -> Word64
l Int
8 forall a. Num a => a -> a -> a
* Word64
7)) forall a. BitWise a => a -> a -> a
.&. Word64
u00                          in

  let !d10 :: Word64
d10 = (Int -> Word64
l Int
8 forall a. Num a => a -> a -> a
* Word64
2 forall a. Num a => a -> a -> a
- (((Word64
x forall a. Shift a => a -> Word64 -> a
.>. Word64
6) forall a. BitWise a => a -> a -> a
.&. (Int -> Word64
l Int
8 forall a. Shift a => a -> Word64 -> a
.<. Word64
1)) forall a. Num a => a -> a -> a
+ ((Word64
x forall a. Shift a => a -> Word64 -> a
.>. Word64
5) forall a. BitWise a => a -> a -> a
.&. (Int -> Word64
l Int
8 forall a. Shift a => a -> Word64 -> a
.<. Word64
1))))              in
  let !b10 :: Word64
b10 = Word64
b04 forall a. Num a => a -> a -> a
- Word64
d10                                                                            in
  let !u10 :: Word64
u10 = (((((Word64
b10 forall a. BitWise a => a -> a -> a
.|. Int -> Word64
h Int
8) forall a. Num a => a -> a -> a
- Int -> Word64
l Int
8) forall a. Shift a => a -> Word64 -> a
.>. Word64
7) forall a. BitWise a => a -> a -> a
.&. Int -> Word64
l Int
8) forall a. BitWise a => a -> a -> a
.|. Int -> Word64
h Int
8) forall a. Num a => a -> a -> a
- Int -> Word64
l Int
8                              in
  let !z10 :: Word64
z10 = (Word64
z00 forall a. BitWise a => a -> a -> a
.&. forall a. BitWise a => a -> a
comp Word64
u10) forall a. BitWise a => a -> a -> a
.|. (((Int -> Word64
h Int
8 forall a. Shift a => a -> Word64 -> a
.>. Word64
1) forall a. BitWise a => a -> a -> a
.|. (Int -> Word64
l Int
8 forall a. Num a => a -> a -> a
* Word64
5)) forall a. BitWise a => a -> a -> a
.&. Word64
u10)                         in

  let !d20 :: Word64
d20 = (Int -> Word64
l Int
8 forall a. Num a => a -> a -> a
* Word64
2 forall a. Num a => a -> a -> a
- (((Word64
x forall a. Shift a => a -> Word64 -> a
.>. Word64
4) forall a. BitWise a => a -> a -> a
.&. (Int -> Word64
l Int
8 forall a. Shift a => a -> Word64 -> a
.<. Word64
1)) forall a. Num a => a -> a -> a
+ ((Word64
x forall a. Shift a => a -> Word64 -> a
.>. Word64
3) forall a. BitWise a => a -> a -> a
.&. (Int -> Word64
l Int
8 forall a. Shift a => a -> Word64 -> a
.<. Word64
1))))              in
  let !b20 :: Word64
b20 = Word64
b10 forall a. Num a => a -> a -> a
- Word64
d20                                                                            in
  let !u20 :: Word64
u20 = (((((Word64
b20 forall a. BitWise a => a -> a -> a
.|. Int -> Word64
h Int
8) forall a. Num a => a -> a -> a
- Int -> Word64
l Int
8) forall a. Shift a => a -> Word64 -> a
.>. Word64
7) forall a. BitWise a => a -> a -> a
.&. Int -> Word64
l Int
8) forall a. BitWise a => a -> a -> a
.|. Int -> Word64
h Int
8) forall a. Num a => a -> a -> a
- Int -> Word64
l Int
8                              in
  let !z20 :: Word64
z20 = (Word64
z10 forall a. BitWise a => a -> a -> a
.&. forall a. BitWise a => a -> a
comp Word64
u20) forall a. BitWise a => a -> a -> a
.|. (((Int -> Word64
h Int
8 forall a. Shift a => a -> Word64 -> a
.>. Word64
1) forall a. BitWise a => a -> a -> a
.|. (Int -> Word64
l Int
8 forall a. Num a => a -> a -> a
* Word64
3)) forall a. BitWise a => a -> a -> a
.&. Word64
u20)                         in

  let !d30 :: Word64
d30 = (Int -> Word64
l Int
8 forall a. Num a => a -> a -> a
* Word64
2 forall a. Num a => a -> a -> a
- (((Word64
x forall a. Shift a => a -> Word64 -> a
.>. Word64
2) forall a. BitWise a => a -> a -> a
.&. (Int -> Word64
l Int
8 forall a. Shift a => a -> Word64 -> a
.<. Word64
1)) forall a. Num a => a -> a -> a
+ ((Word64
x forall a. Shift a => a -> Word64 -> a
.>. Word64
1) forall a. BitWise a => a -> a -> a
.&. (Int -> Word64
l Int
8 forall a. Shift a => a -> Word64 -> a
.<. Word64
1))))              in
  let !b30 :: Word64
b30 = Word64
b20 forall a. Num a => a -> a -> a
- Word64
d30                                                                            in
  let !u30 :: Word64
u30 = (((((Word64
b30 forall a. BitWise a => a -> a -> a
.|. Int -> Word64
h Int
8) forall a. Num a => a -> a -> a
- Int -> Word64
l Int
8) forall a. Shift a => a -> Word64 -> a
.>. Word64
7) forall a. BitWise a => a -> a -> a
.&. Int -> Word64
l Int
8) forall a. BitWise a => a -> a -> a
.|. Int -> Word64
h Int
8) forall a. Num a => a -> a -> a
- Int -> Word64
l Int
8                              in
  let !z30 :: Word64
z30 = (Word64
z20 forall a. BitWise a => a -> a -> a
.&. forall a. BitWise a => a -> a
comp Word64
u30) forall a. BitWise a => a -> a -> a
.|. (((Int -> Word64
h Int
8 forall a. Shift a => a -> Word64 -> a
.>. Word64
1) forall a. BitWise a => a -> a -> a
.|.  Int -> Word64
l Int
8     ) forall a. BitWise a => a -> a -> a
.&. Word64
u30)                         in

  let !p00 :: Word64
p00 = Word64 -> Word64
lsb (Word64
z30 forall a. Shift a => a -> Word64 -> a
.>. Word64
6 forall a. BitWise a => a -> a -> a
.&. Int -> Word64
l Int
8)                                                              in
  let !r00 :: Word64
r00 = ((Word64
p00 forall a. Num a => a -> a -> a
+ ((Word64
z30 forall a. Shift a => a -> Word64 -> a
.>. forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word64
p00 forall a. BitWise a => a -> a -> a
.&. Word64
0x3f)) forall a. BitWise a => a -> a -> a
.&. Word64
0x3f)) forall a. BitWise a => a -> a -> a
.|. (Word64
p00 forall a. Shift a => a -> Word64 -> a
.>. Word64
8)) forall a. BitWise a => a -> a -> a
.&. Word64
0x7f  in
  Word64
r00
{-# INLINE findUnmatchedClose #-}