저작권 안내: 저작권자표시 Yes 상업적이용 No 컨텐츠변경 No

스프링5 입문

JSP 2.3

JPA 입문

DDD Start

인프런 객체 지향 입문 강의

특정 시간 동안 실행 횟수를 제한하기 위한 라이브러를 검색해서 아래 3가지 정도를 찾았다.

이 글에서는 각 라이브러리의 사용법을 간단하게 살펴본다.

Guava RateLimiter

Guava에 포함된 RateLimiter를 사용하면 초당 실행 횟수를 제한할 수 있다. 이 클래스를 사용하려면 다음 의존을 추가한다.

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>26.0-jre</version>
</dependency>

사용 방법은 다음과 같다.

private RateLimiter limiter = RateLimiter.create(4.0); // 초당 4개

public void someLimit() {
    if (limiter.tryAcquire()) { // 1개 사용 요청
        // 초과하지 않음
        ... 코드1 // 초당 4번까지 실행 가능

    } else {
        // 제한 초과

    }
}

RateLimiter.create() 메서드는 초당 몇 개를 허용할지를 인수로 받는다. 위 예의 경우 4.0을 값으로 주었는데 이는 초당 4개를 허용함을 뜻한다. 이 값을 0.2로 주면 초당 0.4개를 허용하므로 5초당 1개를 허용한다.


실행 횟수를 초과했는지 검사할 때 tryAcquire() 메서드를 사용한다. 이 메서드는 허용하는 횟수를 초과하지 않았으면 true를 리턴하고 초과했으면 false를 리턴한다. 따라서 위 코드는 someLimit() 메서드의 '코드1'을 초당 4번까지 실행한다. 만약 1초 이내에 5번을 실행하면 그 중 한 번은 tryAcquire() 메서드가 false를 리턴한다.


RateLimiter는 실행 가능 시점을 분배하는 방식을 사용한다. 예를 들어 다음과 같이 초당 실행 가능한 횟수를 5.0으로 지정하고 0.1초마다 tryAcquire() 메서드를 실행한다고 하자.


RateLimiter limiter = RateLimiter.create(5.0);


Timer timer = new Timer(true);


timer.scheduleAtFixedRate(new TimerTask() {

    @Override

    public void run() {

        if (limiter.tryAcquire()) {

            log.info("!! OK");

        } else {

            log.warn("XX");

        }

    }

}, 0, 100); // 0.1초마다 실행


Thread.sleep(1500);


위 코드를 실행한 결과는 다음과 같다. 이 결과를 보면 "!! OK"와 "XX"가 번갈아 출력된 것을 알 수 있다. 즉 초당 5.0으로 횟수를 제한했을 때 1초에 10번 tryAcquire()를 실행하면 연속해서 5번 실행 가능한 게 아니고 1초에 5번 실행 가능한 시점이 분산되는 것을 알 수 있다.

17:27:39.503 [Timer-0] INFO guava.RateLimiterTest - !! OK
17:27:39.596 [Timer-0] WARN guava.RateLimiterTest - XX
17:27:39.695 [Timer-0] INFO guava.RateLimiterTest - !! OK
17:27:39.797 [Timer-0] WARN guava.RateLimiterTest - XX
17:27:39.898 [Timer-0] INFO guava.RateLimiterTest - !! OK
17:27:39.998 [Timer-0] WARN guava.RateLimiterTest - XX
17:27:40.098 [Timer-0] INFO guava.RateLimiterTest - !! OK
17:27:40.197 [Timer-0] WARN guava.RateLimiterTest - XX
17:27:40.297 [Timer-0] INFO guava.RateLimiterTest - !! OK
17:27:40.396 [Timer-0] WARN guava.RateLimiterTest - XX
17:27:40.498 [Timer-0] INFO guava.RateLimiterTest - !! OK
17:27:40.594 [Timer-0] WARN guava.RateLimiterTest - XX
17:27:40.695 [Timer-0] INFO guava.RateLimiterTest - !! OK
17:27:40.795 [Timer-0] WARN guava.RateLimiterTest - XX
17:27:40.897 [Timer-0] INFO guava.RateLimiterTest - !! OK
17:27:40.997 [Timer-0] WARN guava.RateLimiterTest - XX


[노트]

RateLimiter의 내부 구현은 1초 동안 사용하지 않은 개수를 누적한다. 예를 들어 RateLimiter.create(10)으로 만든 RateLimiter를 1초 동안 사용하지 않았다면 5개가 누적되어 이후 1초 동안은 10개를 사용할 수 있다.


RateLimitJ

RateLimitJ는 Redis, Hazelcast를 이용해서 시간 당 실행 횟수를 제한할 수 있다. 메모리를 이용한 구현도 지원하므로 Redis나 Hazelcast가 없어도 사용할 수 있다. 이 글에서는 인메모리 구현의 사용법을 살펴본다. 인메모리 구현을 사용하려면 다음 의존을 추가한다. Redis를 이용한 구현을 사용하는 방법은 https://github.com/mokies/ratelimitj 사이트를 참고한다.


<dependency>

    <groupId>es.moki.ratelimitj</groupId>

    <artifactId>ratelimitj-inmemory</artifactId>

    <version>0.5.0</version>

</dependency>


RateLimitJ를 이용한 실행 횟수 제한 방법은 다음과 같다.


// 1분에 10개 제한

RequestLimitRule limitRule = RequestLimitRule.of(Duration.ofMinutes(1), 10);

RequestRateLimiter rateLimiter =

        new InMemorySlidingWindowRequestRateLimiter(limitRule);


if (rateLimiter.overLimitWhenIncremented("key")) {

    // 제한 초과


} else {

    // 초과하지 않음


}


RequestLimitRule은 제한 규칙을 적용한다. RequestLimitRule.of() 메서드를 이용해서 제한 규칙을 생성하는데 첫 번째 파라미터는 시간 범위이고 두 번째 파라미터는 제한 횟수이다. 위 코드는 1분 동안 10으로 제한하는 규칙을 생성한다.


이 규칙을 사용해서 InMemorySlidingWindowRequestRateLimiter 객체를 생성하면 사용할 준비가 끝난다.


RequestRateLimiter#overLimitWhenIncremented(key) 메서드는 특정 시간 동안 지정한 횟수를 초과했는지 검사한다. 초과했으면 true를 리턴하고 초과하지 않았으면 false를 리턴한다. 따라서 이 메서드가 false를 리턴할 때 기능을 실행하면 된다.


overLimitWhenIncremented() 메서드는 인수로 key를 받는다. 이 key 별로 규칙을 적용한다. 예를 들어 URI 마다 실행 횟수를 제한하고 싶다면 다음과 같이 key로 URI를 사용하면 된다.


// 각 URI마다 실행 횟수 제한

if (rateLimiter.overLimitWhenIncremented(request.getRequestURI())) {

    // 해당 URI에 대한 제한 초과


} else {

    // 해당 URI에 대한 접근 허용


}


Guava의 RateLimiter와 달리 RateLimitJ는 지정한 횟수에 다다를 때까지 실행을 허용하고 그 이후로는 시간이 지날 때까지 실행을 허용하지 않는다. 예를 들어 다음 코드를 보자.


RequestLimitRule limitRule = RequestLimitRule.of(Duration.ofSeconds(1), 5);

RequestRateLimiter rateLimiter =

        new InMemorySlidingWindowRequestRateLimiter(limitRule);


Timer timer = new Timer(true);


timer.scheduleAtFixedRate(new TimerTask() {

    @Override

    public void run() {

        if (rateLimiter.overLimitWhenIncremented("key")) {

            log.warn("XX"); // 제한 초과로 실행하지 않음

        } else {

            log.info("!! OK"); // 제한을 초과하지 않아 실행함

        }

    }

}, 0, 100);


Thread.sleep(1500);


이 코드는 1초 당 5개로 제한하는 RequestRateLimiter를 사용하고 0.1초마다 한 번씩 기능을 실행하고 있다. 이 코드를 실행하면 다음과 같이 처음 5개 요청을 실행하고 그 이후 1초가 지날 때까지 5개 요청은 제한 초과로 실행하지 않은 것을 알 수 있다.


17:46:38.061 [Timer-0] INFO ratelimitj.RateLimitJTest - !! OK

17:46:38.130 [Timer-0] INFO ratelimitj.RateLimitJTest - !! OK

17:46:38.230 [Timer-0] INFO ratelimitj.RateLimitJTest - !! OK

17:46:38.330 [Timer-0] INFO ratelimitj.RateLimitJTest - !! OK

17:46:38.430 [Timer-0] INFO ratelimitj.RateLimitJTest - !! OK

17:46:38.531 [Timer-0] WARN ratelimitj.RateLimitJTest - XX

17:46:38.632 [Timer-0] WARN ratelimitj.RateLimitJTest - XX

17:46:38.733 [Timer-0] WARN ratelimitj.RateLimitJTest - XX

17:46:38.833 [Timer-0] WARN ratelimitj.RateLimitJTest - XX

17:46:38.931 [Timer-0] WARN ratelimitj.RateLimitJTest - XX

17:46:39.033 [Timer-0] INFO ratelimitj.RateLimitJTest - !! OK

17:46:39.134 [Timer-0] INFO ratelimitj.RateLimitJTest - !! OK

17:46:39.235 [Timer-0] INFO ratelimitj.RateLimitJTest - !! OK

17:46:39.330 [Timer-0] INFO ratelimitj.RateLimitJTest - !! OK

17:46:39.432 [Timer-0] INFO ratelimitj.RateLimitJTest - !! OK


Bucket4j

Bucket4j는 hazelcast, infinispan을 이용한 구현 외에 인메모리 구현을 지원한다. 이 글에서는 인모메리 구현을 이용한 횟수 제한에 대해 살펴본다. 다른 구현에 대한 내용은 https://github.com/vladimir-bukhtoyarov/bucket4j 문서를 참고한다.


인메모리 구현을 사용하려면 다음 의존을 추가한다.


<dependency>

    <groupId>com.github.vladimir-bukhtoyarov</groupId>

    <artifactId>bucket4j-core</artifactId>

    <version>4.0.1</version>

</dependency>


사용법은 다음과 같다.


// 1초에 5개 사용 제한

Bandwidth limit = Bandwidth.simple(5, Duration.ofSeconds(1));

// 버킷 생성

Bucket bucket = Bucket4j.builder().addLimit(limit).build();


if (bucket.tryConsume(1)) { // 1개 사용 요청

    // 초과하지 않음


} else {

    // 제한 초과

    

}


Bandwith는 지정한 시간 동안 제한할 개수를 지정한다. 위 코드는 1초 동안 5개를 허용하는 Bandwith를 생성한다. 이 Bandwith를 이용해서 Bucket을 생성한다. Bucket#tryConsume() 메서드는 사용할 개수를 인수로 받으며, 사용 가능할 경우 true를 리턴하고 사용 가능하지 않으면 false를 리턴한다.



[노트]

Bucket4j는 다중 Bandwidth를 지원한다. 또한 사용 가능 개수를 시간이 흘러감에 따라 점진적으로(greedy) 채우는 방식과 시간 간격마다 채우는 방식을 지원한다. 이에 대한 내용은 Bucket4j 문서를 참고한다.



Posted by 최범균 madvirus

댓글을 달아 주세요

JSTL 1.2의 <fmt:formatDate> 태그는 LocalDateTime과 같이 자바 8부터 제공하는 시간 타입에 대한 포맷팅 출력을 지원하지 않는다. 그래서 JSP에서 LocalDateTime 값을 지정한 형식에 맞춰 출력해주는 간단한 태그 파일을 만들었다.


아래의 태그 파일을 /WEB-INF/tags 폴더에 formatDateTime.tag 이름으로 만들었다.


<%@ tag body-content="empty" pageEncoding="utf-8" %>

<%@ tag import="java.time.format.DateTimeFormatter" %>

<%@ tag trimDirectiveWhitespaces="true" %>

<%@ attribute name="value" required="true" 

              type="java.time.temporal.TemporalAccessor" %>

<%@ attribute name="pattern" type="java.lang.String" %>

<%

if (pattern == null) pattern = "yyyy-MM-dd";

%>

<%= DateTimeFormatter.ofPattern(pattern).format(value) %>


JSP 코드에서는 다음과 같이 태그 파일을 사용해서 원하는 형식으로 값을 출력한다.


<%@ page contentType="text/html; charset=utf-8" %>

<%@ taglib prefix="tf" tagdir="/WEB-INF/tags" %>

<!DOCTYPE html>

<html>

<head>

    <title>회원 조회</title>

</head>

<body>

    ...

    <tf:formatDateTime

            value="${mem.registerDateTime}" 

            pattern="yyyy-MM-dd" />

    ...

</body>

</html>


Posted by 최범균 madvirus

댓글을 달아 주세요


"[팁] j2ssh-maverick를 이용한 SCP + 키이용 파일 복사"에서 SCP 복사를 위해 j2ssh-maverick를 이용했는데, j2ssh-maverick를 이용해서 SFTP 파일 다운로드도 처리했다. 메이븐 의존 설정은 동일하니 이전글을 참고하면 된다.


SFTP로 특정 폴더의 전체 파일을 다운로드받는 코드는 다음과 같다. 아이디, 암호를 이용해서 인증을 처리했는데, 키파일을 이용하고 싶다면 이전글을 참고한다.


String host = "원격서버";

int port = 22;

String remoteUser = "download";


SshClient ssh = null;

try {

    SshConnector con = SshConnector.createInstance();

    ssh = con.connect(new SocketTransport(host, port), remoteUser);

    Ssh2PasswordAuthentication auth = new Ssh2PasswordAuthentication();

    auth.setUsername(remoteUser);

    auth.setPassword(password);

    int authResult = ssh.authenticate(auth);

    if (authResult != SshAuthentication.COMPLETE) {

        throw new RuntimeException("authFail = " + authResult);

    }

    SftpClient sftp = new SftpClient(ssh);

    sftp.setTransferMode(SftpClient.MODE_BINARY);

    FileTransferProgress progress = createFileTransferProgress();

    sftp.copyRemoteDirectory(

            "/home/download/files", // 다운로드할 원격 서버 폴더

            "/data/local/files", // 복사할 파일을 저장할 로컬 폴더 경로

            false, // recursive: true면 하위 폴더까지 포함

            false, // sync: 동기화 여부, true면 원격 폴더에 존재하지 않는 파일을 삭제

            true, // commit: true면 실제 작업을 수행

            progress); // 진척도를 통지받을 객체

    sftp.exit();

} catch (SshException | IOException | SftpStatusException | ChannelOpenException

        | TransferCancelledException e) {

    logger.error("fail to download", e);

    throw new RuntimeException(e);

} finally {

    if (ssh != null)

        try {

            ssh.disconnect();

        } catch (Exception ex) {

        }

}


progress를 생성할 때 사용한 createFileTransferProgress() 메서드는 다음과 같다. FileTransferProgress를 알맞게 구현하면 파일을 얼마나 다운로드했는지 추적할 수 있다.


private FileTransferProgress createFileTransferProgress() {

    return new FileTransferProgress() {

        @Override

        public void started(long bytesTotal, String remoteFile) {

            logger.info("download start: {}", remoteFile);

        }


        @Override

        public void progressed(long bytesSoFar) {

        }


        @Override

        public boolean isCancelled() {

            return false;

        }


        @Override

        public void completed() {

            logger.info("download done");

        }

    };

}


j2ssh-maverick를 사용하면 폴더 뿐만 아니라 개별 파일에 대한 업로드, 다운로드도 처리할 수 있다. j2ssh-maverick가 제공하는 다양한 기능은 https://github.com/sshtools/j2ssh-maverick에서 확인할 수 있다.

Posted by 최범균 madvirus

댓글을 달아 주세요

이번에 프로젝트를 진행하면서 자바 코드로 작성한 배치 처리 프로그램에서 SCP로 파일을 외부 서버로 전송할 일이 생겼다. 검색을 하고 몇 개를 훑어본 뒤에 j2ssh-maverick을 사용하기로 결정했다.


SCP 파일 복사에 사용할 key 파일 생성


ssh-keygen 명령어로 키 파일을 생성한다.


$ ssh-keygen -t rsa

Generating public/private rsa key pair.

Enter file in which to save the key (/home/madvirus/.ssh/id_rsa):

Created directory '/home/madvirus/.ssh'.

Enter passphrase (empty for no passphrase):

Enter same passphrase again:

Your identification has been saved in /home/madvirus/.ssh/id_rsa.

Your public key has been saved in /home/madvirus/.ssh/id_rsa.pub.

The key fingerprint is:

SHA256:....생략..... madvirus@mvpc

The key's randomart image is:

+---[RSA 2048]----+

|o. .+** .        |

|. ..=o =         |

|.o +.o. o        |

|. *o.o.  o       |

| ..Eo  .S        |

|+o= +   .        |

|+*.* +   .       |

|+.* *   .        |

|o*oo ...         |

+----[SHA256]-----+



명령어를 실행하고 나면 홈 디렉토리의 .ssh 폴더에 비밀키 id_rsa 파일과 공개키 id_rsa.pub 파일이 생성된다.


공개키 내용을 복사할 원격 서버의 authorized_keys 파일에 추가


SCP로 파일을 복사할 원격 서버 계정의 authorized_keys 파일에 공개키 파일을 추가한다. 원격 서버의 홈 디렉토리에 .ssh 디렉토리가 없다면 .ssh 디렉토리를 생성한다. 단 권한은 700으로 설정한다. ~/.ssh/authorized_keys 파일이 없다면 authorized_keys 파일도 생성한다. 이 파일의 권한은 600으로 설정한다.


-원격서버에 scp에 사용할 계정으로 로그인

$ cd ~

$ mkdir .ssh

$ chmod 700 .ssh

$ touch .ssh/authorized_keys

$ chmod 600 .ssh/authorized_keys


.ssh 폴더와 authorized_keys 파일의 권한이 올바르지 않으면 sshd는 SSH 연결을 허용하지 않는다. 이에 대한 내용은 http://man.openbsd.org/sshd를 참고한다.


원격 서버에 ~/.ssh 폴더와 ~/.ssh/authorized_keys 파일을 생성했다면 공개키 파일의 내용을 원격서버의 authorized_keys 파일에 추가한다. 아래 명령어를 사용하면 간편하게 추가할 수 있다.


cat ~/.ssh/id_rsa.pub | ssh 계정@원격서버주소 'cat >> ~/.ssh/authorized_keys'



프로젝트에 의존 추가


j2ssh-maverick을 사용하려면 다음의 의존을 pom.xml 파일에 추가한다.


<dependency>

    <groupId>com.sshtools</groupId>

    <artifactId>j2ssh-maverick</artifactId>

    <version>1.5.5</version>

</dependency>


j2ssh-maverick과 키 파일을 이용한 SCP 복사


앞서 생성한 비밀키 파일인 id_rsa를 이용해서 로컬의 파일을 원격지 서버에 전송하는 코드를 작성할 차례이다. 전체 코드는 다음과 같다.


File keyFilePath = new File("id_rsa 파일 경로");

String remoteHost = "원격서버주소";

String remoteUser = "batch";

File localFile = new File("전송할 로컬 파일");

String remotePath = "/home/batch/file";

SshClient ssh = null;

try {

    SshConnector con = SshConnector.createInstance();

    byte[] pkKey = FileCopyUtils.copyToByteArray(keyFilePath);

    SshPrivateKeyFile pkf = SshPrivateKeyFileFactory.parse(pkKey);

    SshKeyPair pair = pkf.toKeyPair("");


    ssh = con.connect(new SocketTransport(remoteHost, 22), remoteUser);


    Ssh2PublicKeyAuthentication sshAuth = new Ssh2PublicKeyAuthentication();

    sshAuth.setPrivateKey(pair.getPrivateKey());

    sshAuth.setPublicKey(pair.getPublicKey());

    int authResult = ssh.authenticate(sshAuth);


    if (authResult == SshAuthentication.COMPLETE) {

        ScpClient scpClient = new ScpClient(localFile, ssh);

        scpClient.put(localFile.getAbsolutePath(), remotePath, false);

        scpClient.exit();

    } else {

        // 인증에 실패한 경우, 알맞은 처리

    }

} finally {

    if (ssh != null)

        try {

            ssh.disconnect();

        } catch (Exception ex) {

        }

}


인증에 실패할 경우 원격서버의 .ssh 디렉토리 권한과 .ssh/authorized_keys 파일의 권한이 올바른지 확인해본다.


j2ssh-maverick에 대한 다양한 내용은 https://github.com/sshtools/j2ssh-maverick 사이트에서 확인할 수 있다.



Posted by 최범균 madvirus

댓글을 달아 주세요

이번에는 파서 콤비네이터(parser combinator)를 구현해 보자. 파서 콤비네이터는 파서를 조합해서(연결해서) 새로운 파서를 만드는 기법이다. 파싱에 기초가 되는 파서를 만들고 이들 파서를 조합해서 상위 수준의 파서를 만들게 되는데, 이를 이용하면 재귀 하향 파서와 동일한 파서를 만들 수 있다.


파서의 입력과 출력


파서 콤비네이터에서 각 파서는 입력으로 토큰스트림(토큰 버퍼)을 받으면 결과로 파싱 결과를 리턴한다. 파싱 결과에는 파싱 성공 여부, 파싱을 통해 생성된 결과, 사용할 토큰스트림이 포함된다.


ParseResult result = parser.parse(tokenBuffer);

// result.isSuccess() : 성공 여부

// result.getValue() : 파싱 결과 값

// result.getTokenBuffer() : 이후 파싱에서 사용할 토큰스트림


예를 들어, 아래 문법에서 ALLOW, DENY, COMMA, IPRANGE는 개별 토큰에 매칭되는 단말 기호이다.


config : allowOrDenyDeclList orderDecl?;

allowOrDenyDeclList : allowOrDenyDecl*;

allowOrDenyDecl : allowDecl | denyDecl;

allowDecl : ALLOW IPRANGE;

denyDecl : DENY IPRANGE;

orderDecl : ORDER orderChoice;

orderChoice : allowDeny | denyAllow;;

allowDeny : ALLOW COMMA DENY;

denyAllow : DENY COMMA ALLOW; 

ORDER : 'order';

ALLOW : 'allow';

DENY : 'deny';

COMMA : ','

IPRANGE : DIGIT+ '.' DIGIT+ '.' DIGIT+ '.' DIGIT+ ( ('/' | '-') DIGIT+)?;


이들 단말 기호를 위한 파서를 TerminalParser라고 해 보자. 이 경우 TerminalParser는 다음과 같이 해당 타입의 토큰을 만나면 파싱에 성공하고, 다른 타입의 토큰을 만나면 파싱에 실패한다.


// TT_ORDER 타입 토큰을 파싱하는 파서

TerminalParser parser = new TerminalParser(TokenType.TT_ORDER);


TokenBuffer tokens = new TokenBuffer(asList(orderToken, allowToken));


ParseResult result = parser.parse(tokens);

// result.isSuccess() -> true : tokens의 첫 번째 토큰이 TT_ORDER 타입이므로 파싱 성공

// result.getValue() -> "order" : 파싱에 성공했으므로 파싱 결과 존재

// result.getTokenBuffer() -> [allowToken] : orderToken은 parser가 파싱해서 사용


ParseResult result2 = parser.parse(result.getTokenBuffer());

// result.isSuccess() -> false : 토큰버퍼의 첫 번째 토큰(allowToken)이 TT_ORDER가 아니므로 실패

// result.getValue() -> null : 파싱 실패했으므로 결과 없음

// result.getTokenBuffer() -> [allowToken]


파싱에 성공하면 토큰을 사용하므로 토큰 버퍼가 다음 토큰으로 이동하고, 파싱에 실패하면 토큰 버퍼 위치가 바뀌지 않는다.


Parser, Action, ParseResult


모든 파서 구현은 동일한 방식으로 동작한다. 즉, 토큰 버퍼를 입력으로 받고 결과로 ParseResult를 리턴한다. 따라서 파서를 위한 상위 타입을 다음과 같이 정의해 볼 수 있다.


public abstract class Parser<I,R> {


    private Action<I,R> action = null;


    public Parser(Action<I,R> action) {

        this.action = action;

    }


    public abstract ParseResult<R> parse(TokenBuffer tokenBuffer);


    protected R action(I input) {

        return action.tranform(input);

    }


}


파서는 파싱 과정에서 입력 결과물을 새로운 결과물로 변환하는데 이때 Action을 사용한다. 이 Action에 입력을 주면 결과로 변환된 값을 생성하는데, 이때 입력과 출력 타입이 각각 I와 R이 된다.

  • parse() 메서드 : 추상 메서드로 각 파서마다 알맞게 구현한다.
  • action() 메서드와 action 필드 : action을 이용해서 변환하는 기능이다. 모든 하위 파서에서 사용한다. 

Action의 정의는 다음과 같다.


public interface Action<I, R> {

    R tranform(I input);

}


ParseResult는 다음과 같다.


public class ParseResult<R> {

    private boolean success;

    private R value;

    private TokenBuffer tokenBuffer;


    public ParseResult(boolean success, R value, TokenBuffer tokenBuffer) {

        this.success = success;

        this.value = value;

        this.tokenBuffer = tokenBuffer;

    }


    public boolean isSuccess() {

        return success;

    }


    public R getValue() {

        return value;

    }


    public TokenBuffer getTokenBuffer() {

        return tokenBuffer;

    }


}


TerminalParser 구현


문법 구조에서 단말 기호를 파싱하는 TerminalParser를 만들어보자.


public class TerminalParser<R> extends Parser<String, R> {

    private TokenType type;


    public TerminalParser(TokenType type, Action<String, R> action) {

        super(action);

        this.type = type;

    }


    @Override

    public ParseResult<R> parse(TokenBuffer tokenBuffer) {

        Token token = tokenBuffer.currentToken();

        if (token.getType() == type) {

            tokenBuffer.moveNext();

            R result = action(token.getValue());

            return new ParseResult(true, result, tokenBuffer);

        } else {

            return new ParseResult(false, null, tokenBuffer);

        }

    }

}


TerminalParser는 단말 파서로 개별 토큰을 파싱한다. 예를 들어, "allow"나 "order"와 같은 토큰을 파싱할 때 TerminalParser를 사용한다. TerminalParser는 파싱 가능한 토큰 타입을 가지며, 현재 토큰이 지정한 토큰 타입과 일치하면 action()을 이용해서 토큰 값을 변환한다.


토큰 값은 String이므로, TerminalParser의 입력은 String이 된다. 이런 이유로 TerminalParser<R>은 입력이 String 타입인 Parser<String,R>을 상속받는다.


다음은 TerminalParser의 사용 예다.


TerminalParser<String> allowParser = new TerminalParser<>(TokenType.TT_ALLOW, v -> v);


TerminalParser<IpRange> ipRangeParser = 

        new TerminalParser<>(TokenType.TT_IPRANGE, v -> new IpRange(v));


TokenBuffer tokens = new TokenBuffer(

    asList(

        new Token(TokenType.TT_ALLOW, "allow"), 

        new Token(TokenType.TT_IPRANGE, "1.2.3.4")

    ));


ParseResult<String> result1 = allowParser.parse(tokens);

// result1.isSuccess() : true, result1.getValue() : "allow"


ParseResult<IpRange> result2 = ipRangeParser.parse(result1.getTokenBuffer());

// result2.isSuccess() : true, result2.getValue() : IpRange("1.2.3.4")


시퀀스 파서


다음을 보자.


orderDecl : ORDER orderChoice;


orderDecl을 파싱하는 파서는 ORDER와 orderChoice를 순서대로 파싱해야 한다. 여기서 ORDER와 orderChoice를 위한 파서가 존재한다고 가정해 보자. orderDecl 파서는 ORDER 파서와 orderChoice 파서를 차례대로 실행한 뒤 두 파서의 결과를 이용해서 새로운 결과를 만들면 된다. ORDER 파서가 파싱에 성공하고 orderChoice 파서가 파싱에 실패하면 orderDecl은 파싱에 실패한다. ORDER 파서와 orderChoice 파서가 모두 성공해야 orderDecl은 파싱에 성공한다.


SequenceParser는 순서에 맞게 한 개 이상의 파서를 차례대로 실행하고 각 파서의 결과를 모아서 새로운 결과를 만든다. n개의 파서의 결과를 사용하므로 Action의 입력값은 List가 된다. 중간에 파싱에 성공하지 못하는 파서가 존재하면 SequenceParser는 파싱에 실패한다.


SequenceParser의 구현 코드는 다음과 같다. 지네릭 타입 파라미터 때문에 코드가 다소 복잡하다.


public class SequenceParser<I,R,T> extends Parser<List<R>,T> {


    // parsers에 속한 각 Parser의 입력과 출력 타입은 서로 다를 수 있기 때문에

    // I는 parsers에 속한 각 Parser의 입력 타입의 공통 상위 타입이다.

    // 비슷하게 R은 각 Parser의 출력 타입의 공통 상위 타입이다.

    private List<? extends Parser<? extends I,? extends R>> parserList;


    public SequenceParser(List<? extends Parser<? extends I,? extends R>> parsers,

                              Action<List<R>,T> action) {

        super(action);

        if (parsers == null || parsers.size() == 0) {

            throw new IllegalArgumentException("no parsers");

        }

        parserList = parsers;

    }


    @Override

    public ParseResult<T> parse(TokenBuffer tokenBuffer) {

        int pos = tokenBuffer.currentPosition();

        Iterator<? extends Parser<? extends I,? extends R>> parserIter = parserList.iterator();

        Parser<? extends I,? extends R> firstParser = parserIter.next();

        ParseResult<? extends R> lastResult = firstParser.parse(tokenBuffer);

        if (lastResult.isSuccess()) {

            List<R> values = new ArrayList<>();

            values.add(lastResult.getValue());

            while (parserIter.hasNext() && lastResult.isSuccess()) {

                lastResult = parserIter.next().parse(tokenBuffer);

                if (lastResult.isSuccess()) {

                    values.add(lastResult.getValue());

                } else {

                    throw new MatchingTokenNotFoundException();

                }

            }

            T ret = action(values);

            return new ParseResult(true, ret, tokenBuffer);

        } else {

            tokenBuffer.resetPosition(pos);

            return new ParseResult(false, null, tokenBuffer);

        }

    }

}


SequenceParser는 n개의 Parser를 입력받는다. 이 Parser들의 입력을 I, 출력을 R이라고 했을 때, SequenceParser는 R의 List를 입력받아 T 타입의 결과를 만든다. 따라서 값을 변환해주는 Action의 입력 타입이 List<R>이고 결과 타입이 T가 된다.


parse() 코드를 보면 첫 번째 Parser를 이용해서 먼저 파싱한다. 첫 번째 Parser가 파싱에 성공하면, 이후 나머지 파서를 이용해서 차례대로 파싱을 진행한다. 첫 번째 Parser가 파싱에 성공한 이후 나머지 Parser에서 파싱에 실패하면 문법에 맞지 않다는 것을 의미하므로 익셉션을 발생시킨다. 모든 Parser가 파싱에 성공하면 action() 메서드를 이용해서 각 Parser의 결과를 담은 List 객체를 변환한다.


다음은 SequenceParser의 사용 예다.


SequenceParser<String, String, Boolean> allowDeny =

    new SequenceParser<>(asList(allowParser, commandParser, denyParser), 

    vals -> true); // Action<List<String>,Boolean>>


ParseResult<Boolean> result = allowDeny.parse(tokenBuffer);

if (result.isSuccess()) {

    Boolean value = result.getValue();

    ...

}


allowParser, commandParser, denyParser는 모두 입력과 출력이 String 타입이기 때문에 SequenceParser의 두 타입 파라미터 값으로 String, String을 주었다. 또한, 파싱 결과 타입으로 Boolean을 사용한다. 따라서, Action은 입력이 List<String>이고 출력은 Boolean이 된다.


allowParser, commandParser, denyParser가 모두 파싱에 성공하면 각각 결과 값으로 "allow", ",", "deny"를 생성한다. 따라서 Action에 전달되는 List는 ["allow", ",", "deny"]가 된다. 위 코드에서는 Action을 위한 람다식의 vals 파라미터가 List로서 ["allow", ",", "deny"] 값을 갖게 된다.


참고로 SequenceParser<String, String, Boolean> 타입은 Parser<List<String>, Boolean>의 하위 타입이므로 다음과 같이 할당 가능하다.


Parser<List<String>, Boolean> allowDeny =

    new SequenceParser<>(asList(allowParser, commandParser, denyParser), 

    vals -> true);


반복 파서


다음 문법을 보자.


allowOrDenyDeclList : allowOrDenyDecl*;

 

이 문법은 allowOrDenyDecl이 0번 이상 반복해서 출현함을 뜻한다. 이런 반복을 처리하기 위한 파서는 파싱에 실패할 때 까지 동일 파서를 반복해서 실행하면 된다. 반복 처리를 위한 RepetitionParser는 다음과 같다.


public class RepetitionParser<I,R,T> extends Parser<List<R>,T> {

    private boolean oneOrMore;

    private Parser<I,R> parser;


    public RepetitionParser(boolean oneOrMore, Parser<I,R> parser, Action<List<R>, T> action) {

        super(action);

        if (parser == null) {

            throw new IllegalArgumentException("no parser");

        }

        this.oneOrMore = oneOrMore;

        this.parser = parser;

    }


    @Override

    public ParseResult<T> parse(TokenBuffer tokenBuffer) {

        List<R> values = new ArrayList<>();

        ParseResult<R> lastResult = parser.parse(tokenBuffer);

        if (lastResult.isSuccess()) {

            values.add(lastResult.getValue());

        }

        // oneOrMore가 true면 최소 한 번은 파싱 성공 필요

        if (oneOrMore && !lastResult.isSuccess()) {

            return new ParseResult<>(false, null, tokenBuffer);

        }

        // 파싱에 실패할 때까지 반복해서 파싱

        while (lastResult.isSuccess()) {

            lastResult = parser.parse(tokenBuffer);

            if (lastResult.isSuccess()) {

                values.add(lastResult.getValue());

            }

        }

        T ret = action(values);

        return new ParseResult(true, ret, tokenBuffer);

    }

}


RepetitionParser는 동일한 내용을 반복해서 파싱하므로, 파싱할 때 사용할 파서를 인자로 받는다. parse() 메서드는 이 파서를 이용해서 파싱을 한다. oneOrMore는 최소 1번 이상 파싱에 성공해야 할지 여부를 지정한다. oneOrMore가 true면 최소 한 번 이상 파싱에 성공해야 한다. oneOrMore가 true인데 첫 번째 파싱에 실패하면 실패 결과를 리턴한다.


parse() 메서드는 최초 한 번 파싱을 수행한 뒤, while을 이용해서 파싱에 실패할 때까지 파싱을 반복해서 수행한다. while()이 종료되면 action()을 이용해서 파싱 결과 List를 변환하고, 파싱 성공 결과를 리턴한다.


선택 파서


다음을 보자.


orderChoice: allowDeny | denyAllow;


orderChoice는 allowDeny나 denyAllow 중 하나가 일치하면 파싱에 성공한다. 이를 위한 ChoiceParser는 다음과 같이 구현할 수 있다.


public class ChoiceParser<I,R,T> extends Parser<R,T> {

    private List<? extends Parser<? extends I,? extends R>> parsers;


    public ChoiceParser(List<? extends Parser<? extends I, ? extends R>> parsers,

                           Action<R,T> action) {

        super(action);

        if (parsers == null || parsers.size() == 0) {

            throw new IllegalArgumentException("no parsers");

        }

        this.parsers = parsers;

    }


    @Override

    public ParseResult<T> parse(TokenBuffer tokenBuffer) {

        int pos = tokenBuffer.currentPosition();

        ParseResult<? extends R> lastResult;

        Iterator<? extends Parser<? extends I,? extends R>> parserIter = parsers.iterator();

        do {

            Parser<? extends I,? extends R> parser = parserIter.next();

            lastResult = parser.parse(tokenBuffer);

        } while (parserIter.hasNext() && !lastResult.isSuccess());

        if (lastResult.isSuccess()) {

            T ret = action(lastResult.getValue());

            return new ParseResult<>(true, ret, tokenBuffer);

        } else {

            tokenBuffer.resetPosition(pos);

            return new ParseResult<>(false, null, tokenBuffer);

        }

    }

}


ChoiceParser는 파싱할 때 사용할 Parser 목록을 전달받는다. SequenceParser와 마찬가지로 각 파서의 입력과 출력을 위한 공통 상위 타입으로 I와 R을 사용한다. 


parse() 메서드는 parsers의 파서를 차례대로 이용해서 파싱을 시도한다. 파싱에 성공하면 do-while을 중단해서 나머지 파서를 진행하지 않는다.


do-while 종료 후 파싱에 성공한 파서가 존재하면 해당 파싱 결과를 action()으로 변환하고 성공 결과를 리턴한다. 파싱에 성공한 파서가 존재하지 않으면 실패 결과를 리턴한다.


옵션 파서


마지막으로 만들 파서는 다음을 처리하기 위한 파서이다.


config : allowOrDeny* orderDecl?;


orderDecl은 존재할 수도 있고 없을 수도 있다. config를 파싱하는데 orderDecl이 없어도 파싱에 실패하지 않는다. 이를 파싱하기 위한 OptionParser는 다음과 같다.


public class OptionParser<I,R> extends Parser<I,Optional<R>> {

    private Parser parser;


    public OptionParser(Parser<I,R> parser) {

        super(null);

        if (parser == null)

            throw new IllegalArgumentException();


        this.parser = parser;

    }


    @Override

    public ParseResult<Optional<R>> parse(TokenBuffer tokenBuffer) {

        int pos = tokenBuffer.currentPosition();

        ParseResult<R> result = parser.parse(tokenBuffer);

        if (result.isSuccess()) {

            return new ParseResult(true, Optional.ofNullable(result.getValue()), tokenBuffer);

        } else {

            tokenBuffer.resetPosition(pos);

        }

        return new ParseResult(true, Optional.empty(), tokenBuffer);

    }


}


OptionParser는 파싱 결과가 존재할 수도 있고 없을 수도 있기 때문에, 결과 값으로 Optional을 사용한다. 내부적으로 parser의 파싱 결과가 성공이든 실패든 OptionParser 자체는 성공을 결과로 리턴한다. 내부적으로 파싱에 성공하면 성공 결과 값을 갖는 Optional을 생성해서 ParserResult를 리턴하고, 그렇지 않으면 값이 없는 Optional을 이용해서 ParserResult를 리턴한다.


파서 콤비네이터를 이용한 IpFilter 파서 구현


필요한 파서를 모두 구현했다. 남은 건 이들 파서를 조합해서 IpFilter를 위한 파서를 만드는 일만 남았다. 지네릭 타입이 막 출현해서 코드가 다소 혼란스러울 수 있는데, 그런 경우 지네릭 타입 관련 부분을 지우고 코드를 보면 도움이 될 것이다.


여기서 만들 IpFilterCombiParser는 내부적으로 앞서 구현한 파서들을 조합해서 파싱을 처리한다. 이 클래스는 먼저 문법에서 단말 부분의 파싱을 위한 TerminalParser를 정의한다.


public class IpFilterCombiParser {

    // termianl

    private TerminalParser<String> allowParser

            new TerminalParser<>(TokenType.TT_ALLOW, v -> v);

    private TerminalParser<String> denyParser

            new TerminalParser<>(TokenType.TT_DENY, v -> v);

    private TerminalParser<IpRange> iprangeParser

            new TerminalParser<>(TokenType.TT_IPRANGE, v -> new IpRange(v));

    private TerminalParser<String> orderParser

            new TerminalParser<>(TokenType.TT_ORDER, v -> v);

    private TerminalParser<String> commaParser

            new TerminalParser<>(TokenType.TT_COMMA, v -> v);


각 TerminalParser는 한 개 토큰 타입에 해당하는 토큰을 파싱한다. iprangeParser는 파싱 결과로 IpRange를 생성하고 나머지는 토큰 값을 그대로 파싱 결과로 사용한다.


다음은 문법에서 아래 부분을 위한 코드이다.


allowOrDenyDeclList : allowOrDenyDecl*;

allowOrDenyDecl : allowDecl | denyDecl;

allowDecl : ALLOW IPRANGE;

denyDecl : DENY IPRANGE;


이 문법을 위한 파서는 다음과 같다.


public class IpFilterCombiParser {

    ...


    // allowDecl : ALLOW iprange;

    private SequenceParser<String, Object, Tuple2<String,IpRange>> allowDecl =

            new SequenceParser<>(

                    Arrays.asList(allowParser, iprangeParser),

                    vals -> new Tuple2<>((String)vals.get(0), (IpRange)vals.get(1))

            );


    // denyDecl : DENY iprange;

    private SequenceParser<String, Object, Tuple2<생략>> denyDecl =

            new SequenceParser<>(

                    Arrays.asList(denyParser, iprangeParser),

                    vals -> new Tuple2<>((String)vals.get(0), (IpRange)vals.get(1))

            );


    // allowOrDenyDecl : allowDecl | denyDecl

    private ChoiceParser<String, Tuple2<생략>, Tuple2<생략>> allowOrDenyDecl =

            new ChoiceParser(Arrays.asList(allowDecl, denyDecl), val -> val);


    // allowOrDenyDeclList : allowOrDenyDecl*

    private RepetitionParser<Tuple2<생략>, Tuple2<생략>, List<Tuple2<생략>>> allowOrDenyList =

            new RepetitionParser(false, allowOrDenyDecl, vals -> vals);



Tuple2는 별도로 만든 클래스로서 두 개의 값을 갖는 객체를 의미한다. 이 타입을 만든 이유는 allowDecl이나 denyDecl을 파싱한 결과로 ("allow", IpRange) 또는 ("deny", IpRange)를 생성하기 위함이다. (자바도 튜플을 지원하는 날이 오겠지.)


allowDecl은 allowParser와 iprangeParser를 차례대로 파싱하는 SequenceParser이다. allowParser의 결과는 String이고 IprangeParser의 결과는 IpRange이므로 Action에 전달되는 객체는 List<Object>이다. 따라서, Action 실행을 위한 람다식은 List의 첫 번째 값을 String으로 타입 변환하고 두 번째 값을 IpRange로 타입 변환한 뒤, 이 두 값을 이용해서 Tuple<String, IpRange> 객체를 생성하고 있다.


// allowDecl의 Action을 위한 람다식: vals은 List<Object>

vals -> new Tuple2<>((String)vals.get(0), (IpRange)vals.get(1))


allowOrDenyDecl은 allowDecl과 denyDecl 중 하나를 이용해서 파싱하고, 그 결과로 Tuple2를 생성한다. allowDecl과 denyDecl이 모두 결과로 Tuple2를 리턴하므로, allowOrDenyDecl의 Action은 성공한 파서의 결과를 그대로 리턴한다. (람다식을 보면 val -> val 인데, 이는 입력 받은 값을 그대로 리턴함을 뜻한다.)


allowOrDenyList는 allowOrDenyDecl을 반복해서 파싱한다. allowOrDenyDecl의 출력은 Tuple이므로, allowOrDenyList는 List<Tuple>을 결과로 리턴한다.


다음으로 만들 파서는 다음 문법을 처리한다.


orderDecl : ORDER orderChoice;

orderChoice : allowDeny | denyAllow;;

allowDeny : ALLOW COMMA DENY;

denyAllow : DENY COMMA ALLOW; 


이를 위한 각 파서는 다음과 같다.


    // allowDeny : ALLOW ',' DENY;

    private SequenceParser<String, String, Boolean> allowDeny =

            new SequenceParser<>(Arrays.asList(allowParser, commaParser, denyParser), 

                                       vals -> true);


    // denyAllow : DENY ',' ALLOW

    private SequenceParser<String, String, Boolean> denyAllow =

            new SequenceParser<>(Arrays.asList(denyParser, commaParser, allowParser), 

                                       vals -> false);


    // orderChoice: allowDeny | denyAllow

    private Parser<Boolean, Boolean> orderChoice =

            new ChoiceParser<>(Arrays.asList(allowDeny, denyAllow), val -> val);


    // orderDecl : ORDER orderChoice

    private SequenceParser<Object, Object, Boolean> orderDecl =

            new SequenceParser<>(Arrays.asList(orderParser, orderChoice), 

                                       vals -> (Boolean)vals.get(1));


"order allow, deny"에서 allowDeny가 파싱하는 부분은 "allow,deny" 부분이다. 이는 IpFilter가 allow를 먼저 적용함을 뜻한다. IpFilter에서 적용 순서는 boolean 타입으로 관리하므로 allowDeny는 이를 위한 파싱 결과로 boolean 타입인 true를 리턴한다. 비슷하게 denyAllow는 파싱 결과로 false를 리턴한다.


orderChoice는 allowDeny나 denyAllow 중 하나를 이용해서 파싱하고 파싱에 성공한 파서의 결과 값을 그대로 리턴한다.


orderDecl의 Action 처리 코드를 보자. 이 코드의 vals는 List<Object>인데 첫 번째 값은 "order" 문자열(orderParser의 결과값)이고 두 번째 값은 Boolean 타입 값(orderChoice의 결과값)이다. 최종적으로 필요한 값은 적용 순서를 위한 Boolean 값이므로 두 번째 원소 값을 리턴한다.


이제 남은 문법은 다음 하나다.


config : allowOrDenyList orderDecl?


이를 위한 파서는 다음과 같다.


    // orderDecl?

    private OptionParser<List<Object>, Boolean> orderDeclOpt = new OptionParser<>(orderDecl);


    // config : allowOrDeny* orderDecl?;

    private SequenceParser<Object, Object, IpFilter> configParser =

            new SequenceParser<>(

                    Arrays.asList(allowOrDenyList, orderDeclOpt),

                    (vals) -> {

                        IpFilter filter = new IpFilter();


                        List<Tuple2<String, IpRange>> ipranges

                                 (List<Tuple2<String, IpRange>>) vals.get(0);

                        ipranges.forEach(tuple -> {

                            if (tuple.e1.equals("allow")) {

                                filter.addAllowIpRange(tuple.e2);

                            } else {

                                filter.addDenyIpRange(tuple.e2);

                            }

                        });


                        Optional<Boolean> allowFirstOpt = (Optional<Boolean>) vals.get(1);

                        filter.setAllowFirst(allowFirstOpt.orElse(true));

                        return filter;

                    });


configParser의 Action을 위한 람다식은 최종적으로 IpFilter를 생성한다. 이 람다식에 전달되는 List의 첫 번째 값은 allowOrDenyList의 결과 값이고 두 번째 값은 orderDeclOpt의 결과 값이다. 


allowOrDenyList의 결과는 List<Tuple2<String, IpRange>>이므로 이 값을 읽어와 IpFilter에 허용 IpRange와 차단 IpRange로 등록한다.


orderDeclOpt의 결과는 Optional<Boolean>이다. 그런데, orderDeclOpt는 옵션 파서이므로 값이 있을 수도 있고 없을 수도 있다. 이런 이유로 위 코드에서는 Optional의 orElse() 메서드를 사용해서 값이 없는 경우 true를 사용하도록 했다.


필요한 파서는 다 만들었다. 남은 것은 configParser를 이용해서 입력을 파싱하고 결과를 생성하는 것이다. 이와 관련된 코드는 다음과 같다.


    private TokenBuffer tokenBuffer;


    private Exception occuredException;

    private IpFilter result;


    public IpFilterCombiParser(TokenBuffer tokenBuffer) {

        this.tokenBuffer = tokenBuffer;

    }


    public void parse() {

        try {

            ParseResult<IpFilter> parseResult = configParser.parse(tokenBuffer);

            if (parseResult.isSuccess()) {

                if (tokenBuffer.currentToken().getType() == TokenType.TT_EOF) {

                    this.result = parseResult.getValue();

                } else {

                    throw new MatchingTokenNotFoundException();

                }

            }

        } catch(Exception e) {

            occuredException = e;

        }

    }


    public Optional<IpFilter> getResult() {

        return Optional.ofNullable(result);

    }


    public boolean isSuccess() {

        return !isFailed();

    }


    public boolean isFailed() {

        return occuredException != null;

    }


}


다 만들었으니 사용할 차례이다.


IpFilterCombiParser parser = new IpFilterCombiParser(tokens);

parser.parse();

if (parser.isSuccess()) {

    Optional<IpFilter> filterOpt = parser.getResult();

    IpFilter filter = filterOpt.get();

}



Posted by 최범균 madvirus

댓글을 달아 주세요

지난 글 "파서 놀이 1 - 간단한 렉서 만들기(http://javacan.tistory.com/entry/파서놀이-1-간단렉서)"에서 정규 표현식을 이용해서 토큰을 만들어주는 간단한 렉서를 구현해봤는데, 이제 파서를 만들어 보자. 여기서 만들 파서는 재귀 하향 파서다.


파싱 결과로 만들 모델


모델은 아주 단순하다. 필터 기능을 제공할 IpFilter와 IP 범위를 담는 IpRanger가 출현한다. 두 클래스는 각각 다음과 같다.


public class IpFilter {

    private boolean allowFirst;

    private List<IpRange> allowIpRangeList = new ArrayList<>();

    private List<IpRange> denyIpRangeList = new ArrayList<>();


    public IpFilter() {

        allowFirst = true;

    }


    public boolean allow(String ip) { ... }


    public void setAllowFirst(boolean allowFirst) {

        this.allowFirst = allowFirst;

    }


    public void addAllowIpRange(IpRange ipRange) {

        allowIpRangeList.add(ipRange);

    }


    public void addAllowIpRanges(List<IpRange> allowIpRanges) {

        allowIpRangeList.addAll(allowIpRanges);

    }


    public void addDenyIpRange(IpRange ipRange) {

        denyIpRangeList.add(ipRange);

    }


    public void addDenyIpRanges(List<IpRange> denyIpRanges) {

        denyIpRangeList.addAll(denyIpRanges);

    }

    ...

}


public class IpRange {

    public IpRange(String range) {

        this.range = range;

    }


    public boolean ipIn(String ip) { ... }

    ...
}


앞선 글에서 렉서 구현에 사용한 설정 예는 다음과 같았다.


allow 172.20.0.128/25

allow 172.30.0.1-255

allow 172.30.1.1

deny 10.10.10.10

order deny, allow


이 글에서 만들 파서는 위 설정을 이용해서 다음과 같은 코드를 실행해서 IpFilter를 생성하는 것이 목표다.


IpFilter ipFilter = new IpFilter();

ipFilter.addAllowIpRange(new IpRange("172.20.0.128/25");

ipFilter.addAllowIpRange(new IpRange("172.30.0.1-255");

ipFilter.addAllowIpRange(new IpRange("172.30.1.1");

ipFilter.addDenyIpRange(new IpRange("10.10.10.10");

ipFilter.setAllowFirst(false); // order deny, allow


재귀 하향 파서(Recursive Descent Parser)


재귀 하향 파서. 이름이 어렵지만, 실제 구현을 보면 생각만큼 어렵지 않다. 문법에서 심볼에 해당하는 메서드를 구하고 각 메서드에서 토큰이 해당 문법을 충족하는지 확인하고 문법을 충족할 경우 필요한 작업(모델 객체 생성과 같은)을 구현하면 된다.


기억을 되살리는 의미에서 문법을 다시 보자.


config : allowOrDenyDeclList orderDecl?;

allowOrDenyDeclList : allowOrDenyDecl*;

allowOrDenyDecl : allowDecl | denyDecl;

allowDecl : ALLOW iprange;

denyDecl : DENY iprange;

orderDecl : ORDER allowDeny | denyAllow;

ORDER : 'order';

allowDeny : ALLOW ',' DENY;

denyAllow : DENY ',' ALLOW; 

ALLOW : 'allow';

DENY : 'deny';

iprange : DIGIT+ '.' DIGIT+ '.' DIGIT+ '.' DIGIT+ ( ('/' | '-') DIGIT+)?;


이 문법의 심볼(config, allowOrDenyDeclList 등)은 각각 파서의 한 개 메서드와 대응한다.


파서 구현의 시작


파서는 파싱 결과로 객체를 생성할 때 필요한 객체를 담기 위한 필드를 갖는다. allowFirst, alloIpRanges, denyIpRanges가 이에 해당한다. 생성자로 TokenBuffer를 받으며, 각 파싱 메서드는 토큰버퍼로부터 토큰을 가져와 문법에 맞는지 확인하고 문법에 맞다면 필요한 작업을 수행한다.


public class IpFilterParser {


    private TokenBuffer tokenBuffer;


    private boolean allowFirst = true;

    private List<IpRange> allowIpRanges = new ArrayList<>();

    private List<IpRange> denyIpRanges = new ArrayList<>();


    private Exception occuredException;


    private IpFilter result;


    public IpFilterParser(TokenBuffer tokenBuffer) {

        this.tokenBuffer = tokenBuffer;

    }


    public void parse() {

        try {

            if (config()) {

                createResult();

            }

        } catch (Exception e) {

            occuredException = e;

        }

    }


config() 메서드는 문법의 최상위 심볼인 config를 처리하는 메서드다. config()가 정상적으로 동작하면 true를 리턴한다. config() 메서드가 true를 리턴하면, 정상적으로 파싱했다는 것을 의미하며 이는  결과적으로 파싱한 결과 값을 allowFirst, allowIpRanges, denyIpRanges에 값을 추가했다는 것을 뜻한다. createResult() 메서드는 이들 값을 이용해서 IpFilter 객체를 생성한다.


config() 실행 도중에 익셉션이 발생하면 occuredException 필드에 보관한다. 이는 뒤에서 파싱을 성공했는지 검사할 때 사용한다.


config 심볼: config() 메서드 구현


config 심볼의 문법은 다음과 같다.


config : allowOrDenyDeclList orderDecl?;


이 문법의 의미는 allowOrDenyDeclList가 오고 그 다음에 orderDecl()이 온다는 뜻이다. 즉, 파서를 구현할 때에는 allowOrDenyDeclList() 파싱에 성공해야 그 다음에 orderDecl() 파싱을 진행해야 한다. 이를 코드로는 다음과 같이 구현할 수 있다.


    public boolean config() {

        // config : allowOrDenyDeclList orderDecl?;

        if (allowOrDenyDeclList()) {

            if (optionalOrderDecl()) {

                return true;

            }

        }

        return false;

    }


config() 메서드는 allowOrDenyDeclList()가 true를 리턴한 경우, 즉 파싱에 성공한 경우에만 그 다음 심볼인 orderDecl을 진행한다. orderDecl은 선택이므로 이를 표현하기 위해 해당 메서드 이름을 optionalOrderDecl()로 설정했다. config 심볼에 따라 config() 메서드는 allowOrDenyDeclList()와 optionalOrderDecl()이 모두 파싱에 성공한 경우 true를 리턴하고 그렇지 않으면 false를 리턴한다.


allowOrDenyDeclList 심볼: allowOrDenyDeclList() 메서드 구현


allowOrDenyDeclList 심볼은 다음과 같다.


allowOrDenyDeclList : allowOrDenyDecl*;


이 심볼은 allowOrDenyDecl이 존재하지 않거나 한 번 이상 존재할 수 있다. 즉, allowOrDenyDecl 문법에 일치하지 않아도 allowOrDenyDeclList()의 파싱은 실패하지 않는다. 단지 어떤 결과도 없을 뿐이다. allowOrDenyDeclList 심볼의 파싱 구현은 다음과 같다.


    private boolean allowOrDenyDeclList() {

        // allowOrDenyDeclList: allowOrDenyDecl*;

        while (allowOrDenyDecl()) {

        }

        return true;

    }


allowOrDenyDecl()이 false를 리턴할 때 까지 반복하는데, 중요한 점은 항상 true를 리턴한다는 점이다. 즉, allowOrDenyDecl()이 파싱을 한 번도 못해도 allowOrDenyDeclList는 파싱에 성공한 것으로 간주한다.


allowOrDenyDecl 심볼 : allowOrDeny() 메서드 및 관련 메서드 구현


allowOrDenyDecl 심볼 및 관련 심볼은 다음과 같다.


allowOrDenyDecl : allowDecl | denyDecl;

allowDecl : ALLOW iprange;

denyDecl : DENY iprange;


allowOrDenyDecl 심볼은 allowDecl이거나 denyDecl 이므로 다음과 같이 파싱 과정을 구현할 수 있다.


    private boolean allowOrDenyDecl() {

        // allowOrDenyDecl : allowDecl | denyDecl;

        if (allowDecl()) {

            return true;

        } else if (denyDecl()) {

            return true;

        }

        return false;

    }


allowDecl()에 성공하면 true를 리턴하고 allowDecl()이 아니면 denyDecl()로 넘어간다. denyDecl()이 성공하면 true를 리턴한다. 둘 다 아니면 false를 리턴한다.


allowDecl 심볼의 파싱 구현이 다소 복잡하다. 실제 토큰을 이용해서 파싱하기 때문이다. allowDecl()의 구현은 다음과 같다.


    private boolean allowDecl() {

        // allowDecl : ALLOW iprange;


        // 토큰 버퍼의 현재 위치 저장

        int save = tokenBuffer.currentPosition();

        boolean parseSuccess = false;

        if (tokenBuffer.currentTokenAndMoveNext().getType() == TokenType.TT_ALLOW) {

            Token token = tokenBuffer.currentTokenAndMoveNext();

            if (token.getType() == TokenType.TT_IPRANGE) {

                allowIpRanges.add(new IpRange(token.getValue())); // IpRange 객체 생성

                parseSuccess = true;

            } else {

                fail("IpRange token expected, but " + token.toString(), token);

            }

        }

        // allowDecl 심볼이 아니면 토큰 버퍼의 위치를 원래대도 되돌림

        if (!parseSuccess) {

            tokenBuffer.resetPosition(save);

        }

        return parseSuccess;

    }


    private void fail(String s, Token token) {

        throw new ParseFailException(s, token);

    }


alloDesc 심볼은 "ALLOW iprange"이므로 TT_ALLOW 타입 토큰과 TT_IPRANGE 타입 토큰이 차례대로 와야 한다. allowDesc() 메서드는 토큰 버퍼에서 토큰을 가져와 차례대로 TT_ALLOW, TT_IPRANGE 타입 토큰인지 확인한다. 두 토큰의 타입이 일치하면 TT_IPRANGE 타입 토큰의 값을 이용해서 IpRange 객체를 생성하고 allowIpRanges 리스트(필드)에 추가한다.


allowDesc() 메서드는 토큰 타입이 일치하지 않는 경우를 대비해 토큰을 가져오기 전 토큰버퍼의 위치를 저장한다. 파싱에 성공하지 않으면 토큰 버퍼를 원래 위치로 되돌린다. 파싱 성공 여부는 partSuccess 변수에 저장한다. 두 토큰이 차례대로 TT_ALLOW, TT_IPRANGE인 경우에만 partSuccess가 true가 되므로 첫 번째 토큰이 TT_ALLOW 타입이 아니면 토큰 버퍼는 원래 위치로 되돌아간다.


첫 번째 토큰이 TT_ALLOW 타입이었는데 두 번째 토큰 타입이 TT_IPRANGE가 아니면 문법에 어긋나는 것이다. 따라서 파싱을 더 이상 진행하지 않고 익셉션을 발생시킨다. 익셉션이 발생하면 최초의 메서드를 실행한 parse() 메서드의 catch 블록에서 익셉션을 처리한다. (앞의 parse() 구현을 보자.)


denyDecl 심볼의 파싱을 처리하는 denyDecl() 메서드는 allowDecl()과 거의 동일하다.


    private boolean denyDecl() {

        // denyDecl : DENY iprange;

        int save = tokenBuffer.currentPosition();

        boolean parseSuccess = false;

        if (tokenBuffer.currentTokenAndMoveNext().getType() == TokenType.TT_DENY) {

            Token token = tokenBuffer.currentTokenAndMoveNext();

            if (token.getType() == TokenType.TT_IPRANGE) {

                denyIpRanges.add(new IpRange(token.getValue()));

                parseSuccess = true;

            } else {

                fail("IpRange token expected, but " + token.toString(), token);

            }

        }

        if (!parseSuccess) {

            tokenBuffer.resetPosition(save);

        }

        return parseSuccess;

    }


흐름 한 판 정리


앞서 config() 메서드를 다시 보자.


    public boolean config() {

        // config : allowOrDenyDeclList orderDecl?;

        if (allowOrDenyDeclList()) {

            if (optionalOrderDecl()) {

                return true;

            }

        }

        return false;

    }


지금까지 구현한 파싱 코드는 allowOrDenyDeclList 심볼과 관련된 내용이다. 메서드의 흐름을 보면 다음과 같음을 알 수 있다.

  • config()  // config : allowOrDenyDeclList orderDecl?
    • allowOrDenyDeclList() // allowOrDenyDeclList : allowOrDenyDecl*
      • while allowOrDenyDecl()  // allowOrDenyDecl : allowDecl | denyDecl
        • if allowDecl() else denyDecl()
    • optionalOrderDecl()
메서드 실행 흐름이 상위 문법에서 하위 문법으로 하향으로 실행되는 것을 알 수 있다.

orderDecl 심볼 : optionalOrderDecl() 메서드

이제 파싱의 남은 과정은 orderDecl 심볼을 파싱하는 optionalOrderDecl() 메서드를 구현하는 것이다. 이 메서드는 다음과 같다.

    private boolean optionalOrderDecl() {
        // orderDecl : ORDER allowDeny | denyAllow;
        int save = tokenBuffer.currentPosition();
        boolean parseSuccess = false;
        Token token = tokenBuffer.currentTokenAndMoveNext();
        if (token.getType() == TokenType.TT_ORDER) {
            if (allowDeny()) {
                parseSuccess = true;
            } else if (denyAllow()) {
                parseSuccess = true;
            } else {
                fail("order keyword must follow 'allow,deny' or 'deny,allow", token);
            }
        }
        if (!parseSuccess) {
            tokenBuffer.resetPosition(save);
        }
        return true;
    }

optionalOrderDecl()은 항상 true를 리턴한다. 그 이유는 TT_ORDER 타입 토큰이 아니라고 해서 파싱에 실패하는 것이 아니기 때문이다. 앞서 config 심볼의 정의를 다시 보자.

config : allowOrDenyDeclList orderDecl?

orderDecl 심볼이 옵션이다. 따라서 orderDecl 심볼은 있어도 되고 없어도 된다. 따라서 orderDecl 심볼을 파싱할 차례에서 TT_ORDER 타입의 토큰이 없다 해도 이 파싱은 실패한 것이 아니다. 단지 orderDecl 심볼이 없는 상태로 파싱에 성공한 것이므로 true를 리턴한다.

첫 번째 토큰이 TT_ORDER인 경우, 이어지는 토큰은 allowDeny()나 denyAllow()로 파싱할 수 있어야 한다. 이 두 메서드가 모두 파싱에 실패하면 문법에 맞지 않은 토큰인 것이므로 익셉션을 발생한다. allowDeny()와 denyAllow()는 각각 다음과 같다.

    private boolean allowDeny() {
        int save = tokenBuffer.currentPosition();
        boolean parseSuccess = false;

        Token order1 = tokenBuffer.currentTokenAndMoveNext();
        if (order1.getType() == TokenType.TT_ALLOW) {
            Token token = tokenBuffer.currentTokenAndMoveNext();
            if (token.getType() == TokenType.TT_COMMA) {
                Token order2 = tokenBuffer.currentTokenAndMoveNext();
                if (order2.getType() == TokenType.TT_DENY) {
                    parseSuccess = true;
                    allowFirst = true;
                }
            }
        }
        if (!parseSuccess) {
            tokenBuffer.resetPosition(save);
        }
        return parseSuccess;
    }

    private boolean denyAllow() {
        int save = tokenBuffer.currentPosition();
        boolean parseSuccess = false;

        Token order1 = tokenBuffer.currentTokenAndMoveNext();
        if (order1.getType() == TokenType.TT_DENY) {
            Token token = tokenBuffer.curentTokenAndMoveNext();
            if (token.getType() == TokenType.TT_COMMA) {
                Token order2 = tokenBuffer.currentTokenAndMoveNext();
                if (order2.getType() == TokenType.TT_ALLOW) {
                    parseSuccess = true;
                    allowFirst = false;
                }
            }
        }

        if (!parseSuccess) {
            tokenBuffer.resetPosition(save);
        }
        return parseSuccess;
    }

allowDeny()가 파싱에 성공하면 allowFirst 필드 값을 true로 설정하고, denyAllow()가 파싱에 성공하면 allowFirst를 false로 설정한다.


파서의 결과 생성


최초의 parse() 메서드는 다음과 같았다.


    public void parse() {

        try {

            if (config()) {

                createResult();

            }

        } catch (Exception e) {

            occuredException = e;

        }

    }


즉, 모든 파싱에 성공하면 createResult()로 파싱 결과를 생성한다. createResult()는 다음과 같이 IpFilter 객체를 생성한다.


    private void createResult() {

        IpFilter ipFilter = new IpFilter();

        ipFilter.setAllowFirst(allowFirst);

        ipFilter.addAllowIpRanges(allowIpRanges);

        ipFilter.addDenyIpRanges(denyIpRanges);

        this.result = ipFilter;

    }


렉서와 파서 붙이기


앞서 구현한 렉서와 파서를 붙이는 건 어렵지 않다. Lexer로 TokenBuffer를 생성하고, 그 TokenBuffer를 파서에 전달한 뒤 파싱을 실행하면 된다. 그리고, 파싱 결과에 따라 결과를 구하면 끝이다.


Lexer lexer = new Lexer(someCode);

TokenBuffer tokens = lexer.tokenize();

IpFilterParser parser = new IpFilterParser(tokens);

parser.parse();

if (parser.isSuccess()) {

    Optional<IpFilter> filterOpt = parser.getResult();

    IpFilter ipFilter = filterOpt.get();

}


이번 글에서 간단한 재귀 하향 파서를 구현의 감을 익혔는데, 다음엔 파서를 조합해서 파서를 만드는 콤비네이터 파서를 구현해보자.

Posted by 최범균 madvirus

댓글을 달아 주세요

다음은 아파치 웹 서버 설정을 일부 따라서 만들 설정이다.


allow 172.20.0.128/25

allow 172.30.0.1-255

allow 172.30.1.1

deny 10.10.10.10

order deny, allow


이 설정은 접근을 허용하거나 차단할 IP 범위를 설정할 목적으로 만들어봤다. 이 글에서는 이 설정을 읽어와 파싱해서 실제 모델로 만들어주는 파서를 만드는 연습을 해 볼까 한다.

이 설정을 위한 BNF는 다음과 같이 작성해 볼 수 있을 것 같다. (BNF는 보는 책이나 문서마다 그 형식이 달라서 작성할 때 마다 헷갈린다.)

config : allowOrDenyDeclList orderDecl;
allowOrDenyDeclList : allowOrDenyDecl*;
allowOrDenyDecl : allowDecl | denyDecl;
allowDecl : ALLOW iprange;
denyDecl : DENY iprange;
orderDecl : ORDER allowDeny | denyAllow;
ORDER : 'order';
allowDeny : ALLOW ',' DENY;
denyAllow : DENY ',' ALLOW; 
ALLOW : 'allow';
DENY : 'deny';
iprange : DIGIT+ '.' DIGIT+ '.' DIGIT+ '.' DIGIT+ ( ('/' | '-') DIGIT+)?;
DIGIT : '0'..'9';

위 문법을 구현한 파서를 바로 만들면 좋겠지만, 그 전에 할일이 하나 있다. 그것은 바로 렉서(lexer)를 만드는 것이다. 범용 프로그래밍 언어를 만들려면 렉서나 파서를 구현하는 것이 복잡하겠지만 여기서 만들 렉서는 매우 제한된 영역을 다루므로 매우 간단하게 구현해 볼 것이다.

간단한 렉서 만들기

정규 표현식을 사용해서 초간단 렉서를 만들어보자. 이 렉서는 설정 문자열을 읽어와 해당 토큰으로 변환해주는 기능을 제공한다. 예를 들어, 다음 설정 정보를 보자.

allow 1.2.3.4

만들어 볼 렉서는 이 설정 문자열로부터 다음과 같은 토큰을 생성한다.

ALLOW(value='allow") WS(value=' ') IPRANGE(value='1.2.3.4')

파서는 이 토큰 스트림으로부터 파싱을 수행해서 최종 결과를 만들게 된다.


렉서가 생성할 토큰의 종류는 다음과 같다.

  • ALLOW : 'allow' 키워드
  • DENY : 'deny' 키워드
  • IPRANGE : IP 범위 값
  • ORDER : 'order' 키워드
  • COMMA : 콤마(,)
  • WS : 공백문자(' \t\r\n')
토큰 종류는 다음 특징을 갖는다.
  • 각 토큰 종류에 포함되는 토큰 값을 정규표현식을 사용해서 표현할 수 있다. 예를 들어, 'allow' 키워드는 "^allow"로, 공백문자는 "^(\s)*"로 표현할 수 있다.
  • 공백 문자는 파서에 전달할 필요가 없는 토큰이다.

이 두 정보를 담는 열거 타입 TokenType은 토큰을 분리할 때 사용할 정규 표현식과 결과에 포함되는지 여부를 담는다.


public enum TokenType {

    TT_ALLOW("^allow", true),

    TT_DENY("^deny", true),

    TT_ORDER("^order", true),

    TT_IPRANGE("^[0-9]+\\.[0-9]+\\.[0-9]+\\.[0-9]((/|-)[0-9]+)?", true),

    TT_COMMA(",", true),

    TT_WS("^[ \t\r\n]+", false),

    TT_EOF(null, true);


    private String regex;

    private boolean outputIncluded;


    TokenType(String regex, boolean outputIncluded) {

        this.regex = regex;

        this.outputIncluded = outputIncluded;

    }


    public String getRegex() {

        return regex;

    }


    public boolean isOutputIncluded() {

        return outputIncluded;

    }


    public boolean hasRegex() {

        return regex != null && !regex.isEmpty();

    }

}


개별 토큰을 위한 클래스인 Token은 다음과 같다.


public class Token {

    private TokenType type;

    private String value;


    public Token(TokenType type, String value) {

        this.type = type;

        this.value = value;

    }


    public TokenType getType() {

        return type;

    }


    public String getValue() {

        return value;

    }


    // equals() 메서드...

}


TokenType을 이용해서 입력 문자열로부터 토큰을 분리해서 Token 목록을 제공하는 간단한 렉서를 만들어보자. 구현의 단순함을 위해 이 렉서는 문자열을 입력받아 토큰 목록을 리턴한다. 토큰 목록은 다음과 같은 토큰 버퍼에 담아 리턴한다.


import java.util.List;


public class TokenBuffer {

    private List<Token> tokenList;

    private int currentPosition = 0;


    public TokenBuffer(List<Token> tokenList) {

        this.tokenList = tokenList;

    }


    public Token currentToken() {

        return tokenList.get(currentPosition);

    }


    public Token currentTokenAndMoveNext() {

        return tokenList.get(currentPosition++);

    }


    public boolean hasNext() {

        return currentPosition < tokenList.size() - 1;

    }


    public boolean hasCurrent() {

        return currentPosition < tokenList.size();

    }

    public void moveNext() {

        currentPosition++;

    }

    public int currentPosition() {

        return currentPosition;

    }

    ...

}


이제 Lexer 코드를 보자.


import java.util.ArrayList;

import java.util.Iterator;

import java.util.List;

import java.util.regex.Matcher;

import java.util.regex.Pattern;


public class Lexer {


    private String code;

    private List<Token> tokenList = new ArrayList<>();

    private List<TokenTypePattern> typePatterns = new ArrayList<>();


    public Lexer(String code) {

        this.code = code;

        for (TokenType type : TokenType.values()) {

            if (type.hasRegex())

                typePatterns.add(new TokenTypePattern(type));

        }

    }


    public TokenBuffer tokenize() {

        while(matchToken() && !eof()) {

        }

        if (!eof()) {

            // 일치하지 않은 토큰이 존재하는 것임!

            throw new MatchingTokenNotFoundException();

        }

        tokenList.add(new Token(TokenType.EOF, null));

        return new TokenBuffer(tokenList);

    }


    private boolean matchToken() {

        boolean match = false;

        Iterator<TokenTypePattern> patterIter = typePatterns.iterator();

        while(!match && patterIter.hasNext()) {

            TokenTypePattern ttPattern = patterIter.next();

            Matcher matcher = ttPattern.pattern.matcher(code);

            if (matcher.find()) {

                if (ttPattern.type.isOutputIncluded()) {

                    tokenList.add(new Token(ttPattern.type, matcher.group()));

                }

                match = true;

                code = code.substring(matcher.end());

            }

        }

        return match;

    }


    private boolean eof() {

        return code.length() == 0;

    }


    private class TokenTypePattern {

        private TokenType type;

        private Pattern pattern;


        public TokenTypePattern(TokenType type) {

            this.type = type;

            this.pattern = Pattern.compile(type.getRegex());

        }

    }

}


생성자는 토큰을 추출할 문자열을 전달받아 code 필드에 저장한다. 생성자는 TokenType으로부터 TokenTypePattern 리스트를 생성한다. TokenTypePattern은 내부 클래스로 정의되어 있으며, TokenType과 토큰을 식별할 때 사용할 Pattern을 저장한다.


주요 코드는 matchToken() 메서드에 있다. matchToken() 메서드는 TokenTypePattern의 Pattern을 이용해서 code 문자열 앞 부분이 일치하는 TokenType을 검색한다. 일치하는 TokenType이 존재하면 해당 문자열로부터 Token을 생성해서 tokenList에 추가한다. 그리고, code 문자열에서 일치한 부분을 제외한 나머지 부분을 다시 code에 할당한다.


matchToken() 메서드는 일치한 토큰이 존재하면 true를 리턴하고 그렇지 않으면 false를 리턴한다. tokenize() 메서드는 이 리턴 값을 이용해서 계속해서 토큰을 추출할지 여부를 결정한다. tokenize() 메서드는 while을 이용해서 matchToken()이 true를 리턴하고 eof()가 false일 때까지 계속해서 이 과정을 반복한다. eof()는 더 이상 추출할 문자열이 없으면 true를 리턴하므로, tokenize()의 while 문은 TokenType에 일치하는 토큰이 없거나 끝까지 모두 토큰을 추출한 경우 끝이난다.


tokenize()의 while이 끝난 뒤 eof() 여부를 다시 확인하는데, 만약 eof()가 true가 아니면 일치하지 않는 토큰이 존재한다는 것이므로 익셉션을 발생한다. 그렇지 않고 끝까지 토큰을 추출했다면 TokenBuffer를 리턴한다.


간단 Lexer 구현 테스트


테스트 코드를 만들어서 동작을 확인했다.


public class LexerTest {


    @Test

    public void noTokens() throws Exception {

        Lexer lexer = new Lexer("");

        TokenBuffer tokenBuffer = lexer.tokenize();

        assertThat(tokenBuffer.currentToken(), equalTo(eofToken()));

        assertThat(tokenBuffer.hasNext(), equalTo(false));

    }


    @Test

    public void twoTokens() throws Exception {

        Lexer lexer = new Lexer("allow 1.2.3.4");

        TokenBuffer tokenBuffer = lexer.tokenize();

        assertThat(tokenBuffer.currentTokenAndMoveNext(), 

                    equalTo(token(TokenType.TT_ALLOW, "allow")));

        assertThat(tokenBuffer.currentTokenAndMoveNext(), 

                    equalTo(token(TokenType.TT_IPRANGE, "1.2.3.4")));

        assertThat(tokenBuffer.nextTokenAndMoveNext(), equalTo(eofToken()));

        assertThat(tokenBuffer.hasNext(), equalTo(false));

        assertThat(tokenBuffer.hasCurrent(), equalTo(false));

    }


    @Test

    public void invalidToken() throws Exception {

        Lexer lexer = new Lexer("allow 1.2.3.4 noToken");

        try {

            lexer.tokenize();

            fail();

        } catch(MatchingTokenNotFoundException ex) {

        }

    }


    @Test

    public void invalidToken2() throws Exception {

        Lexer lexer = new Lexer("allow 1.2.3.4/");

        try {

            lexer.tokenize();

            fail();

        } catch(MatchingTokenNotFoundException ex) {

        }

    }


    private static Token token(TokenType type, String value) {

        return new Token(type, value);

    }


    private static Token eofToken() {

        return new Token(TokenType.EOF, null);

    }

}


일단 잘 동작하는 것 같다. 다음 글에서는 간단하게 Recursive Descent Parser를 만들어보자.



Posted by 최범균 madvirus

댓글을 달아 주세요

자바8 스트림 API 소개 자료입니다.


Posted by 최범균 madvirus

댓글을 달아 주세요

  1. 제임스최슬링 2014.12.10 17:19 신고  댓글주소  수정/삭제  댓글쓰기

    개발자 입니다.
    구글링이나 네이버링을 통해 자주 오게되는데, 존경스럽습니다.
    제임스 고슬링다음으로 존경합니다.
    많은 지식에 놀랐습니다.많이 참고하겠습니다. 감사합니다.

자바8의 람다식(lambda expression) 소개 자료입니다.



Posted by 최범균 madvirus

댓글을 달아 주세요

  1. ㅎㅎㅎ 2014.09.18 17:55 신고  댓글주소  수정/삭제  댓글쓰기

    와 엄청바꼈네요 잘보고갑니다!

Mockito, Spring MVC Test 등 테스트 코드를 작성하다보면 static import를 사용해서 메서드 이름만 사용하는 경우가 자주 발생한다. 이 때 이클립스에서 메서드 이름만 입력한 뒤에 컨트롤+스페이스 또는 컨트롤+1 을 사용해서 static import를 자동으로 처리하고 싶지만, 아직 여기까진 지원해주지 않고 있다.


그렇다고 static import와 관련된 지원을 아주 받지 못하는 것은 아니다. 다음의 방법으로 지원 받을 수 있다.

  • Window --> Preferences 메뉴 실행
  • Java/Editor/Content Assist/Favorites 메뉴 실행
  • Net Type 또는 New Member 버튼을 클릭한 뒤, static import 코드 지원 대상이 될 타입이나 멤버 추가
내 경우는 아래 그림처럼 테스트 코드에서 주로 사용하는 클래스들을 등록해서 사용하고 있다.




Posted by 최범균 madvirus

댓글을 달아 주세요

  1. 나그네 2014.07.01 08:47 신고  댓글주소  수정/삭제  댓글쓰기

    진짜 이런걸 보면 인텔리J가 왜 좋은지 알것 같네요
    딱 개발에만 집중할 수 있도록 잘 되어있는거 같아요^^

요즘 밤에 틈이 나면 수련을 위한 개인 프로젝트를 진행중인데, 구현하는 과정 중에 클라이언트를 식별하기 위해 세션ID를 생성하는 기능이 필요해졌다. 이 기능을 직접 구현하기가 너무 너무 귀찮아서 자바에서 기본으로 제공하는 UUID 클래스를 사용하기로 마음 먹었다.


UUID의 사용법은 간단한데, 조금 마음에 안 들었던 건 UUID를 문자열로 변환할 때 그 길이가 다소 길다는 것이었다. 아래 코드처럼 UUID를 문자열로 변환하면 32자 ('-' 포함하면 36자)이다.


UUID uuid = UUID.randomUUID();

System.out.println(uuid.toString()); // --> "bf6f75a4-a1e9-4c0b-9b17-e9b6b5c0e5ed"


세션ID로 쓰기에 너무 길어서 이걸 조금이라도 줄여보고 싶은 마음에 16진수가 아닌 알파벳 대소문자와 특수문자 몇 개를 더 보태 64진수로 표현하는 코드를 만들어 보았다. 사실 만들었다기 보다는 자바에 있는 변환 코드를 복사해서 약간 보탰다.


    public static String toUnsignedString(long i, int shift) {

        char[] buf = new char[64];

        int charPos = 64;

        int radix = 1 << shift;

        long mask = radix - 1;

        long number = i;

        do {

            buf[--charPos] = digits[(int) (number & mask)];

            number >>>= shift;

        } while (number != 0);

        return new String(buf, charPos, (64 - charPos));

    }


    final static char[] digits = {

            '0', '1', '2', '3', '4', '5', '6', '7',

            '8', '9', 'a', 'b', 'c', 'd', 'e', 'f',

            'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',

            'o', 'p', 'q', 'r', 's', 't', 'u', 'v',

            'w', 'x', 'y', 'z', 'A', 'B', 'C', 'D',

            'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L',

            'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T',

            'U', 'V', 'W', 'X', 'Y', 'Z', '_', '*' // '.', '-'

    };


toUnsignedString() 메서드에서 i는 변환할 문자열을, shift는 변환 대상 진수를 위한 값을 나타낸다. 예를 들어, shift가 1이면 2진수를, shift가 3이면 8진수를, shift가 6이면 64진수를 의미한다. 여기서 코드를 보면서 눈치를 챈 사람도 있겠지만, 숫자 1을 왼쪽으로 shfit 만큼 비트 이동했을 때 나오는 숫자가 변환 대상 진수가 된다.


실제 toUnsignedString()을 이용해서 UUID를 문자열로 변환하면 아래와 같이 10글자를 줄일 수 있는 것을 알 수 있다.


UUID uuid = UUID.randomUUID();

System.out.println(uuid.toString());

// eda788c4-2187-4e3c-9a53-affe69dd4fb5 : 32자 ('-' 포함 36자)


System.out.println(toUnsignedString(uuid.getMostSignificantBits(), 6) + 

                          toUnsignedString(uuid.getLeastSignificantBits(), 6));

// eSDycgxxQUY9FjH*VFTk_R (22자)



Posted by 최범균 madvirus

댓글을 달아 주세요

ip-filter 구현 이야기 발표 자료:



관련 글:





Posted by 최범균 madvirus

댓글을 달아 주세요

ip-filter-core 모듈은 아래와 같이 Config 객체를 이용해서 차단/허용 목록을 설정한다. (ip-filter의 사용법은 https://github.com/madvirus/ip-filter/wiki/HOME_kr 문서를 참고하기 바란다.)


Config config = new Config();

config.setAllowFirst(true);

config.setDefaultAllow(false);

config.allow("1.2.3.4"); // 허용 IP 추가

config.allow("10.20.30.40");

config.deny("101.102.103.104"); // 차단 IP 추가


IpFilter ipFilter = IpFilters.create(config);


ipFilter.accept("1.2.3.4"); // true

ipFilter.accept("101.102.103.104"); // false


코드로 설정하는 것이 필요할 때가 있지만, 아래와 같은 문자열을 이용할 수 있다면 파일이나 운영툴 등에서 쉽게 설정할 수 있을 것이다.


# 주석

order allow,deny

default true

allow from 1.2.3.4

allow from 1.2.5.* # 뒤에 주석

allow from 201.202.203.10/64

deny from all


위 문자열을 읽어와서 Config 객체를 생성하려면 문자열을 알맞게 파싱해 주어야 하는데, 파싱을 어떻게 할까 고민하다가 최근에 학습하고 있는 스카라(Scala)의 콤비네이터 파서(Conbinator parser)를 사용해 보기로 했다. 스카라는 자체적으로 Context-free grammer 에 따른 파싱 기능을 제공하고 있기 때문에, ANTLR과 같은 별도의 파서 생성기를 사용하지 않아도 된다.


스카라를 이용한 문자열 파서


음,, 먼저 스카라에 익숙하지 않은 분들은 아래 코드가 잘 이해되지 않을 것이다. 그래도 그냥 읽어보기 바란다. 설정 문자열을 파싱하기 위해 작성한 스카라 코드는 아래와 같다. (아래 코드는 order나 default를 여러 줄 입력해도 에러를 발생시키진 않는데, order나 default를 여러번 설정할 경우 오류를 발생시킬지의 여부는 고민 중에 있다.)


class Conf extends JavaTokenParsers {

  override val whiteSpace = """[ \t]+""".r


  def conf: Parser[Config] = repsep(confPart, eol) ^^ (

    x => {

      val config = new Config

      x.foreach(part =>

        part match {

          case ("order", firstAllow: Boolean) => config.setAllowFirst(firstAllow)

          case ("default", defaultAllow: Boolean) => config.setDefaultAllow(defaultAllow)

          case ("allow", ip: String) => config.allow(ip)

          case ("deny", ip: String) => config.deny(ip)

          case _ =>

        })

      config

    }

    )


  def confPart: Parser[Any] = commentPart | orderPart | defaultPart | allowOrDenyPart | emptyLine


  def commentPart: Parser[String] = """#(.*)""".r ^^ (x => x)


  def orderPart: Parser[Tuple2[String, Boolean]] =

    "order" ~ orderValue ~ opt(commentPart) ^^ (x => ("order", x._1._2))


  def orderValue: Parser[Boolean] = {

    "allow" ~ "," ~ "deny" ^^ (x => true) |

      "deny" ~ "," ~ "allow" ^^ (x => false)

  }


  def defaultPart: Parser[Tuple2[String, Boolean]] = 

      "default" ~ booleanValue ^^ (x => ("default", x._2))


  def booleanValue: Parser[Boolean] = "true" ^^ (x => true) | "false" ^^ (x => false)


  def allowOrDenyPart: Parser[Tuple2[String, String]] =

    allow ^^ (x => ("allow", x)) | deny ^^ (x => ("deny", x))


  def allow: Parser[String] = "allow" ~ "from" ~ ipPattern ~ opt(commentPart) ^^ (x => x._1._2)


  def deny: Parser[String] = "deny" ~ "from" ~ ipPattern ~ opt(commentPart) ^^ (x => x._1._2)


  def ipPattern: Parser[String] =

    "all" ^^ (x => "*") |

      """(\d+\.){1,3}(\*)""".r ^^ (x => x) |

      """(\d+\.\d+\.\d+\.\d+\/\d+)""".r ^^ (x => x) |

      """(\d+\.\d+\.\d+\.\d+)""".r ^^ (x => x)


  def emptyLine: Parser[String] = ""


  def eol: Parser[String] = """(\r?\n)+""".r

}


class ConfParser extends Conf {

  def parse(confText: String): Config = {

    val result = parseAll(conf, confText)

    if (result.successful)

      result.get

    else

      throw new ConfParserException(result.toString)

  }

}


Conf 클래스는 문자열을 파싱해서 Config 객체를 생성해주는 기능을 제공하며, ConfParser 클래스는 외부에 파싱 기능을 제공하는 parse() 메서드를 제공한다.


자바 코드에서는 ConfParser 클래스를 이용해서 문자열로부터 Config 객체를 생성할 수 있다.


public class UsingConfParserTestInJava {

    @Test

    public void useConfParser() {

        String confValue =

                "order deny,allow\n" +

                        "allow from 1.2.3.4\n" +

                        "deny from 10.20.30.40\n" +

                        "allow from 101.102.103.*\n" +

                        "allow from 201.202.203.10/64";


        Config config = new ConfParser().parse(confValue);

        assertFalse(config.isAllowFirst());

        assertEquals(config.getAllowList().size(), 3);

    }


응용


문자열로부터 Config 객체를 생성하는 파서를 만들었으니, 이제 파일이나 다른 곳에서 설정 데이터를 읽어와 Config 객체를 만들 수 있게 되었다. 실제 응용은 웹 어플리케이션에서 특정 IP 차단을 위해 작성한 ip-filter-web-simple 에서 사용하였다. (관련 코드는 https://github.com/madvirus/ip-filter/tree/master/ip-filter-web-simple 에서 확인 가능)


package org.chimi.ipfilter.web.impl;


import org.chimi.ipfilter.Config;

import org.chimi.ipfilter.parser.ConfParser;


import java.io.FileReader;

import java.io.IOException;


public class FileConfigFactory extends ConfigFactory {


    @Override

    public Config create(String value) {

        return new ConfParser().parse(readFromFile(value));

    }


    private String readFromFile(String fileName) {

        try {

            return IOUtil.read(new FileReader(fileName));

        } catch (IOException e) {

            throw new ConfigFactoryException(e);

        }

    }


    @Override

    public boolean isReloadSupported() {

        return true;

    }


}



Posted by 최범균 madvirus

댓글을 달아 주세요

지난 글 "IP 필터 만들기 1, 아이디어"에서 트리 구조로 허용/차단 IP 목록을 표시하는 방법을 정리해봤는데, 이번 글에서는 실제 구현을 살펴보도록 하겠다. 참고로, 본 글에서 설명하는 모든 코드는 https://github.com/madvirus/ip-filter 에 공개되어 있으니 참고하기 바란다.


IP 트리 구성을 위한 클래스: IpTree, NumberNode


ip-filter 모듈에서 사용하는 IP 목록은 아래와 같은 방식으로 표현한다.


1.2.3.4

1.2.3.64/26

5.6.7.*

10.20.*

30.*


이를 트리로 표현하기 위해 두 개의 클래스를 작성하였다.

  • IpTree: 트리의 관리 및 특정 IP가 트리로 표현되는지 확인해주는 기능
  • NumberNode: 트리의 각 노드를 표현


NumberNode 구현

NumberNode는 트리의 루트 노드부터 말단 노드까지를 표현한다. 노드는 위 그림에서 보듯 세 가지 종류의 값을 갖는다.
  • 숫자
  • 별표(*)
  • 네트워크주소표현 (예, 128/25)
이를 표현하기 위해 NumberNode 객체의 생성 부분을 아래와 같이 구현하였다.

public class NumberNode {

    private final String number;

    private boolean isSimpleNumber;
    private int filterNumber;
    private int lastValueOfNetworkNumber;
    private boolean allAccept;

    public NumberNode(String number) {
        this.number = number;
        processPattern();
    }

    private static int[] filterNumbers = {
            0x00, // 24
            0x80, // 25
            0xC0, // 26
            0xE0, // 27
            0xF0, // 28
            0xF8, // 29
            0xFC // 30
    };

    private void processPattern() {
        if (number.equals("*")) {
            isSimpleNumber = false;
            allAccept = true;
            return;
        }
        int slashIdx = number.indexOf("/");
        if (slashIdx == -1) {
            isSimpleNumber = true;
            return;
        }
        // 64/26과 같은 네트워크 주소 형식 처리 위한 코드
        this.lastValueOfNetworkNumber = Integer.parseInt(number.substring(0, slashIdx));
        int bitsOfNetworkNumber = Integer.parseInt(number.substring(slashIdx + 1));

        this.filterNumber = filterNumbers[bitsOfNetworkNumber - 24];
        this.isSimpleNumber = false;
    }

위 코드에서 각 필드는 다음과 같다.
  • isSimpleNumber: 값이 숫자면 true, 별표나 네트워크주소 표현이면 false
  • allAccept: 값이 별표면 true, 아니면 false
  • 네트워크 주소 관련 필드 (값 형식이 A/B 인 경우)
    • lastValueOfNetworkNumber: A/B 형식에서 A 값. 예, 128/25 에서 128
    • filterNumber: 데이터 비교시에 사용할 숫자 (뒤에서 설명)
값 일치 여부 확인

NumberNode를 생성한 뒤에, 해당 노드가 특정 숫자와 매칭되는지 여부를 확인하는 기능이 필요하다. 이를 위해 isMatch() 메서드를 아래와 같이 구현하였다.

public class NumberNode {

    private final String number;

    private boolean isSimpleNumber;
    private int filterNumber;
    private int lastValueOfNetworkNumber;
    private boolean allAccept;

    public boolean isMatch(String number) {
        if (allAccept) return true; // this.number가 "*" 인 경우
        if (isSimpleNumber) return this.number.equals(number); // this.number가 숫자인 경우

        // this.number가 A/B 형식인 경우
        int filtered = filterNumber & Integer.parseInt(number);
        return filtered == lastValueOfNetworkNumber;
    }

위 코드는 아래와 같이 작동한다.

NumberNode n1 = new NumberNode("128");
n1.isMatch("10"); // false
n1.isMatch("128"); // true

NumberNode n2 = new NumberNode("*");
n2.isMatch("0"); // true
n2.isMatch("123"); // true

NumberNode n3 = new NumberNode("128/25");
n3.isMatch("128"); // true
n3.isMatch("200"); // true
n3.isMatch("255"); // true
n3.isMatch("127"); // false
n3.isMatch("100"); // false

[박스] 네트워크 주소
"64/26"에 대해 약간의 설명이 필요할 것 같다. 흔히 네트워크 주소라 하면, 아래와 같이 표시한다.

2.4.8.64/26

여기서 숫자들은 각각 한 바이트를 차지하며, 여기서 마지막 64/26은 네트워크 범위를 지정하는 숫자가 된다. 이 예의 경우 64는 네트워크 범위 기준점이 되는 네 번째 바이트의 값이며, 26은 전체 주소에서 네트워크 주소로 사용될 비트 길이가 된다. 위 숫자에서 2.4.8.64는 아래와 같이 비트로 표현할 수 있는데,

00000010 00000100 00001000 01000000 (2 4 8 64)

여기서 앞에서 26개 비트, 즉 아래 값이 2.4.8.64/26 네트워크에서 사용할 네트워크 주소가 된다.

00000010 00000100 00001000 01 (앞에서부터 26비트)

이 네트워크 주소에서 사용할 수 있는 주소 범위는 아래와 같다.

00000010 00000100 00001000 01000000 ~ 
00000010 00000100 00001000 01111111

즉, 마지막 주소로 64 부터 127 까지가 64/26에 해당하는 숫자 범위이다. 따라서, 어떤 주소가 이 네트워크 주소 범위에 포함되는 확인하려면 다음과 같이 64/26에 해당하는 비교 값과 실제 주소 값을 AND 연산해서 네트워크 주소값이 나오는지 확인해보면 된다.

11111111 11111111 11111111 11000000 (필터 위한 비교 값)
00000010 00000100 00001000 01001100 (실제 주소)
---------------------------------- (AND 연산)
00000010 00000100 00001000 01000000 -> 네트워크 주소 값과 일치하므로, 이 주소는 네트워크 범위에 포함

앞서 NumberNode는 이 방식을 사용해서 특정 숫자가 범위에 포함되는 지 확인한다.

자식 노드 생성을 위한 메서드

NumberNode는 자식 노드를 생성/보관/검색하는 기능을 제공함으로써, 뒤에서 설명할 IpTree가 내부적으로 노드를 쉽게 구성할 수 있도록 하였다. 이와 관련된 코드는 아래와 같다.

public class NumberNode {
    ...
    private Map<String, NumberNode> simpleChildNodeMap = new HashMap<String, NumberNode>();
    private List<NumberNode> patternChildNodes = new ArrayList<NumberNode>();

    public NumberNode createOrGetChildNumber(String numberPattern) {
        if (simpleChildNodeMap.containsKey(numberPattern))
            return simpleChildNodeMap.get(numberPattern);

        for (NumberNode patternChild : patternChildNodes)
            if (patternChild.number.equals(numberPattern))
                return patternChild;

        NumberNode childNode = new NumberNode(numberPattern);
        if (childNode.isSimpleNumber)
            simpleChildNodeMap.put(number, childNode);
        else
            patternChildNodes.add(childNode);

        return childNode;
    }

    public NumberNode findMatchingChild(String number) {
        NumberNode simpleChildNode = simpleChildNodeMap.get(number);
        if (simpleChildNode != null) return simpleChildNode;

        for (NumberNode patternChildNode : patternChildNodes)
            if (patternChildNode.isMatch(number))
                return patternChildNode;

        return null;
    }
    ...
}

createOrGetChildNumber() 메서드는 NumberNode는 자식 노드를 두 가지 방식으로 보관한다.
  • 정확한 숫자는 simpleChildNodeMap 에 <숫자값, 자식노드>로 보관 (숫자값이 키)
  • A/B 형식의 패턴 및 "*"은 patternChildNodes 에 추가
createOrGetChildNumber() 메서드는 동일한 숫자를 가진 자식 노드가 존재하면 그 노드를 리턴하고, 존재하지 않으면 새로 생성해서 자식 노드로 추가한다. 이 메서드는 IpTree 클래스가 IP 문자열로부터 트리 노드를 생성할 때 사용된다.

findMatchingChild() 메서드는 입력받은 숫자와 매칭되는 자식 노드를 구해서 리턴해준다. 이 메서드는 IpTree에서 특정 IP 문자열이 트리에 매칭되는 지 확인하기 위해 사용된다.

IpTree 구현

IpTree 클래스는 다음의 두 기능을 제공한다.

  • IP 문자열을 트리로 구성해주는 기능을 제공한다. 
  • 특정 IP 문자열이 트리에 매칭되는지 확인하는 기능을 제공한다.
실제 구현은 아래와 같다.

public class IpTree {
    private NumberNode root = new NumberNode("");

    public void add(String ip) {
        String[] ipNumbers = ip.split("\\.");
        NumberNode node = root;
        for (String number : ipNumbers) {
            node = node.createOrGetChildNumber(number);
        }
    }

    public boolean containsIp(String ip) {
        String[] ipNumbers = ip.split("\\.");
        NumberNode node = root;
        for (String number : ipNumbers) {
            node = node.findChildNumber(number);
            if (node == null)
                return false;
            if (node.isAllAccept())
                return true;
        }
        return true;
    }
}


IpTree 클래스는 아래와 같이 사용한다.


IpTree tree = new IpTree();

tree.add("1.2.3.4");

tree.add("1.2.4.5");

tree.add("1.2.5.*");

tree.add("1.2.6.128/25");


tree.containsIp("1.2.3.4"); // true

tree.containsIp("1.2.3.5"); // false

tree.containsIp("1.2.6.129"); // true

tree.containsIp("1.2.5.4"); // true


실제 IP Filter 기능 구현


IP 필터는 다음과 같이 두 개의 IP 목록을 갖는다.

  • 허용 IP 목록
  • 차단 IP 목록
IP 필터는 이 두 개의 IP 목록을 별도의 IpTree 타입 필드를 이용해서 보관한다. 실제 IpFilter의 구현은 다음과 같다.

public class ConfigIpFilter implements IpFilter {

    private boolean defaultAllow;
    private IpTree allowIpTree;
    private IpTree denyIpTree;
    private boolean allowFirst;

    public ConfigIpFilter(Config config) {
        defaultAllow = config.isDefaultAllow();
        allowFirst = config.isAllowFirst();
        allowIpTree = makeIpTree(config.getAllowList());
        denyIpTree = makeIpTree(config.getDenyList());
    }

    private IpTree makeIpTree(List<String> ipList) {
        IpTree ipTree = new IpTree();
        for (String ip : ipList)
            ipTree.add(ip);
        return ipTree;
    }

    @Override
    public boolean accept(String ip) {
        if (allowFirst) {
            if (allowIpTree.containsIp(ip)) return true;
            if (denyIpTree.containsIp(ip)) return false;
        } else {
            if (denyIpTree.containsIp(ip)) return false;
            if (allowIpTree.containsIp(ip)) return true;
        }
        return defaultAllow;
    }

}

ConfigIpFilter는 Config로부터 허용 IP 목록과 차단 IP 목록을 읽어와 각각을 위한 IpTree를 생성한다. accept() 메서드는 이 IpTree 객체를 이용해서 지정한 IP가 차단 IP인지, 허용 IP인지 여부를 결정한다. 참고로, ConfigIpFilter 클래스의 사용법은 아래와 같다.

    @Test
    public void shouldReturnTrueToAllowedIpAndReturnFalseToDeniedIp() {
        Config config = new Config();
        config.setDefaultAllow(true);
        config.setAllowFirst(true);
        config.allow("1.2.3.4");
        config.allow("1.2.3.5");
        config.allow("1.2.3.64/26"); // // 01xxxxxx 범위 : 64~127
        config.deny("5.6.7.8");
        config.deny("101.102.103.32/27"); // 001xxxxx 범위: 32~63")

        IpFilter ipFilter = new ConfigIpFilter(config);
        assertTrue(ipFilter.accept("1.2.3.4"));
        assertTrue(ipFilter.accept("1.2.3.5"));
        assertTrue(ipFilter.accept("1.2.3.64"));
        assertTrue(ipFilter.accept("1.2.3.65"));
        assertTrue(ipFilter.accept("1.2.3.127"));
    }


성능 확인


ConfigIpFilter의 IP 필터 기능의 성능을 측정해 보았다. 이를 위해 다음의 IP 설정 목록을 차단 목록으로 추가하였다. 이 목록은 37,538 개 이며, 전체 목록은 https://github.com/madvirus/ip-filter/wiki/ip-list-config-for-performance-test 에서 확인할 수 있다.


1.0.1.*

1.0.2.*

1.0.3.*

...

101.253.*  
101.254.*  
103.1.8.*  
...
106.187.34.17
106.187.34.18
106.187.34.19
...
223.223.207.*
223.240.*
223.241.*
...
223.255.252.*
223.255.253.*


이 IP 설정이 포함하는 IP 개수는 약 3억 3천만이다. 


테스트는 아래와 같이 진행하였다.

  • 테스트 과정
    • 위 IP 설정 목록을 이용해서 차단 IP 목록으로 사용하는 IpFilter 객체 생성
    • 테스트 IP 범위 목록 중 랜덤하게 5개의 패턴을 뽑아, 그 패턴에 해당하는 IP 들을 차례대로 테스트 진행
      • 5개의 패턴이 적어 보일 수 있으나, 36.16.0.0~36.37.255.255 범위는 약 144만 개의 IP를 테스트
    • 각 IP를 검사하는 시간을 누적해서 평균 값 구함
  • 이 테스트를 5회 진행
비교 테스트를 위해 두 개의 IpFilter에 대해 테스트를 진행하였다..
  • 트리 기반으로 IP 목록을 유지하는 ConfigIpFilter 클래스
  • List를 이용해서 IP 목록을 유지하는 테스트용 ListIpFilter 클래스 (비교 목적으로 작성)
    • IP 확인 요청이 왔을 때, 허용IP/차단IP 목록을 순차적으로 비교 확인
두 번째 방식의 테스트는 안 하려고 했으나, 비교 자료를 원하시는 분들이 있을 것이기에 넣었다.


성능 비교 결과


테스트는 노트북에 진행했으면 노트북의 사양은 아래와 같다.

  • Intel Core i5-2457M @ 1.6 GHz
  • Windows 7 64bit 
  • JDK 6 (1.6.0_26)

성능 비교 결과 표를 아래와 같이 정리하였다.


[표1] 1개 쓰레드로 실행한 결과

-트리 방식


리스트 방식
회차

실행 회수

실행 시간 합
(밀리초)

실행 시간 평균
(밀리초)

실행 회수

실행 시간 합
(밀리초)

실행 시간 평균
(밀리초)

1

199,680

678

0.003400

50,944

28,631

0.562029

2

1,450,240

3,648

0.002516

1,212,928

181,893

0.152436

3

22,016

196

0.008931

12,800

6,397

0.499768

4

804,352

2,109

0.002622

377,088

152,709

0.404970

5

1,120,256

2,723

0.002431

273,920

14,964

0.054632

  

 평균

0.003980

 

평균 

0.334767


두 방식에서 확연한 속도 차이가 느껴진다. 트리 기반의 IP 필터 기능은 한 개 검사하는 데 0.004 밀리초(즉, 0.000004 초) 걸리는데 반해 리스트 방식은 0.335 밀리초로 (즉, 0.000335 초) 약 80배 이상 차이가 난다. 또한, 트리 방식은 실행 시간 평균이 균일한데 반해, 리스트 방식은 실행 시간 평균 10 배 이상 차이가 나기도 한다.


참고로, 트리 방식과 달리 리스트 방식이 이렇게 들쑥 날쑥한 이유는 리스트 방식이 풀스캔을 하기 때문이다. 트리 방식은 DB에 비교하면 인덱스를 사용해서 검색하는 방식이고, 리스트 방식은 인덱스 없이 전체 데이터를 스캔해서 검색하는 방식이다. 따라서, 리스트 방식에서 비교 대상이 앞쪽에 위치하면 검색 속도가 빠르고, 비교 대상이 뒤쪽에 위치하면 검색 속도가 그 만큼 느려지게 된다.


위와 동일한 테스트를 동시에 10개 쓰레드를 실행해서 테스트 해 보았다. 최대한 동시에 실행되는 효과를 만들기 위해 한 쓰레드가 최대 10만개의 IP만 검사하도록 제한을 걸었다. 테스트 결과는 아래와 같다.


[표2] 10개 쓰레드로 실행한 결과 (1쓰레드 당 최대 10만개까지만 검사)

-

트리 방식


리스트 방식
회차

실행 회수

실행 시간 합
(밀리초)

실행 시간 평균
(밀리초)

실행 회수

실행 시간 합
(밀리초)

실행 시간 평균
(밀리초)

1

695,840

7,592

0.010912

672,033

745,404

1.110667

2

816,640

6,325

0.007746

847,712

837,813

0.988323

3

698,304

6,301

0.009024

720,576

633,170

1.101748

4

901,120

8,216

0.009118

792,000

976,851

1.233398

5

664,096

5,576

0.008397

693,024

1,162,127

1.677894

 

 

 평균

0.009039

 

평균 

1.205352



1개 쓰레드를 이용한 경우와 10개 쓰레드를 이용한 경우를 비교해보면, 트리 방식에 비해 리스트 방식의 평균 실행 시간이 더 크게 증가한 것을 알 수 있다.


비교 목적으로 사용한 ListIpFilter 클래스 코드


트리 구조와 성능 비교 하기 위해 작성한 ListIpFilter의 코드는 아래와 같다.


public class ListIpFilter implements IpFilter {

    private boolean defaultAllow;

    private boolean allowFirst;

    private List<IpPattern> allowIpPatterns = new ArrayList<IpPattern>();

    private List<IpPattern> denyIpPatterns = new ArrayList<IpPattern>();


    public ListIpFilter(Config config) {

        defaultAllow = config.isDefaultAllow();

        allowFirst = config.isAllowFirst();

        for (String ipPattern : config.getAllowList())

            allowIpPatterns.add(new IpPattern(ipPattern));

        for (String ipPattern : config.getDenyList())

            denyIpPatterns.add(new IpPattern(ipPattern));

    }


    @Override

    public boolean accept(String ip) {

        if (allowFirst) {

            if (isAllowIp(ip)) return true;

            if (isDenyIp(ip)) return false;

        } else {

            if (isDenyIp(ip)) return false;

            if (isAllowIp(ip)) return true;

        }

        return defaultAllow;

    }


    private boolean isAllowIp(String ip) {

        for (IpPattern ipPattern : allowIpPatterns) {

            if (ipPattern.isMatch(ip))

                return true;

        }

        return false;

    }


    private boolean isDenyIp(String ip) {

        for (IpPattern ipPattern : denyIpPatterns) {

            if (ipPattern.isMatch(ip))

                return true;

        }

        return false;

    }


    private class IpPattern {


        private String exactMatchingPart;


        private boolean exactMatchingPattern = false;

        private boolean acceptAllPattern = false;

        private boolean rangePattern = false;


        private int fromNumberInRangePattern = 0;

        private int toNumberInRangePattern = 0;


        public IpPattern(String ipPattern) {

            if (ipPattern.endsWith("*")) {

                acceptAllPattern = true;

                exactMatchingPart = ipPattern.substring(0, ipPattern.length() - 1);

            } else {

                int slashIdx = ipPattern.indexOf("/");

                if (slashIdx == -1) {

                    exactMatchingPart = ipPattern;

                    exactMatchingPattern = true;

                } else {

                    int lastDotIdx = ipPattern.lastIndexOf(".");

                    exactMatchingPart = ipPattern.substring(0, lastDotIdx + 1);


                    int rangeNumber = Integer.parseInt(ipPattern.substring(lastDotIdx + 1, slashIdx));

                    int bitLength = Integer.parseInt(ipPattern.substring(slashIdx + 1));


                    rangePattern = true;

                    fromNumberInRangePattern = rangeNumber;

                    switch (bitLength) {

                        case 24:

                            toNumberInRangePattern = fromNumberInRangePattern + 0xFF;

                            break;

                        case 25:

                            toNumberInRangePattern = fromNumberInRangePattern + 0x7F;

                            break;

                        case 26:

                            toNumberInRangePattern = fromNumberInRangePattern + 0x3F;

                            break;

                        case 27:

                            toNumberInRangePattern = fromNumberInRangePattern + 0x1F;

                            break;

                        case 28:

                            toNumberInRangePattern = fromNumberInRangePattern + 0x0F;

                            break;

                        case 29:

                            toNumberInRangePattern = fromNumberInRangePattern + 0x07;

                            break;

                        case 30:

                            toNumberInRangePattern = fromNumberInRangePattern + 0x03;

                            break;

                    }

                }

            }

        }


        public boolean isMatch(String ip) {

            if (exactMatchingPattern)

                return ip.equals(exactMatchingPart);


            if (acceptAllPattern)

                return ip.startsWith(exactMatchingPart);


            if (rangePattern) {

                if (!ip.startsWith(exactMatchingPart)) return false;


                int lastNumberOfIp = Integer.parseInt(ip.substring(exactMatchingPart.length()));

                return lastNumberOfIp >= fromNumberInRangePattern 

                         && lastNumberOfIp <= toNumberInRangePattern;

            }

            return false;

        }

    }

}



참고 자료



Posted by 최범균 madvirus

댓글을 달아 주세요

  1. 2014.08.26 10:15  댓글주소  수정/삭제  댓글쓰기

    비밀댓글입니다

몇 년 전, 이전 직장에서 웹 게임의 CBT를 진행하는데, 갑자기 외부에서의 연결이 급격하게 느려지는 증상이 발생했다. 얼른 웹 서버와 DB에 들어가 봤으나 CPU/네트워크 관련 수치 모두 문제가 없었다. 내부에서의 연결은 문제 없이 잘 들어가졌다. 유관 팀과 함께 조사를 진행하다가 원인을 찾았다. 원인은 "방화벽의 차단 IP 목록"이었다.


방화벽에 등록된 차단 IP에 중국 IP 및 IP 대역들이 등록되어 있었는데, 그 개수가 많아서 트래픽 증가와 함께 방화벽의 CPU 사용률이 높아졌고 이로 인해 방화벽이 느려지는 문제가 발생했다. 웹 게임 서버로 들어오는 웹 요청을 방화벽이 빠르게 처리하지 못하자, 외부 게이머들의 불만이 폭주하기 시작했다. 일단, 방화벽의 IP 차단 목록의 개수를 줄여서 (정확하게는 화이트 리스트의 순위를 위로 올려서) 상황을 벗어났다. 그 당시 차단 IP 개수가 많아져도 성능이 저하되지 않는 IP 차단 모듈을 만들어봐야지라는 생각을 했고, 거의 3년이 지난 요즈음 IP 차단 기능을 제공하는 ip-filter 모듈 제작을 시작해서 0.1 버전을 만들었다.


아이디어


방화벽의 내부 구현을 알 순 없었지만, 검사할 IP 규칙 목록의 개수가 많았을 때 방화벽의 CPU 점유률이 높아지고 검사할 규칙 목록의 개수가 적었을 때 CPU 점유률이 낮아진 것으로 보아, 클라이언트의 IP에 해당하는 검사 규칙이 나타날 때 까지 순차적으로 각 규칙을 확인하는 것 같았다. 방화벽 설정에는 (중국 IP 대역 목록을 포함한) 매우 많은 차단 규칙이 앞쪽에 위치해 있었기 때문에, 클라이언트의 연결 요청이 들어오면 이 많은 차단 규칙을 다 확인한 뒤에 방화벽을 통과할 수 있는 것으로 추정되었다. IP가 규칙에 맞는지 여부를 확인하는 것은 순전히 CPU를 잡아 먹는 연산이기 때문에 동접자수가 증가할수록 CPU 점유률이 높아졌을 거라 생각된다.


그래서, 생각해본 것이 규칙 목록들을 트리 구조로 구성하는 것이었다. 예를 들어, 아래의 규칙에 해당하는 IP를 차단하고 싶다고 하자.

  • 1.2.3.4 (정확한 일치 IP)
  • 1.2.3.128/25 (1.2.3.128 ~ 1.2.3.255 대역)
  • 1.12.13.14 (정확한 일치 IP)
  • 10.20.* (10.20.0.0 ~ 10.20.255.255 대역)
  • 10.30.40.51 (정확한 일치 IP)
  • 10.30.40.52 (정확한 일치 IP)

이 검사 대상 IP 목록을 아래 그림과 같은 트리 형식으로 보관하는 것이다.



이렇게 트리 형식으로 검사할 규칙의 개수에 상관없이 항상 5 레벨 이하의 트리 탐색으로 특정 IP가 검사 규칙에 일치하는지 여부를 알아낼 수 있다. 예를 들어, IP 주소가 "1.12.13.5"라고 하자. 이 경우, 트리 상의 루트->1->12->13 까지는 일치하나 마지막 5레벨에서 IP 주소의 마지막 "5"와 일치하는 노드가 존재하지 않는다. 따라서, "1.12.13.5"는 매칭되는 규칙이 존재하지 않는다. 반면에 IP 주소가 "10.30.40.51"인 경우, 트리 상의 루트->10->30->40->51 에 정확하게 일치하므로, "10.30.40.51"은 매칭되는 규칙이 존재한다.


검사해야 할 규칙 목록이 백 개이든, 천 개이든, 만 개이든 상관없이 항상 5 레벨 이하의 트리 탐색으로 특정 IP가 검사 규칙에 걸리는지 확인할 수 있다. 따라서, 규칙 개수가 증가하더라도 앞서 순차적 검사와 달리 더 적은 CPU 시간을 사용할 거라 예상된다. 예를 들어, 규칙이 만 개이고 클라이언트 IP가 어떤 규칙에도 일치하지 않는다면, 만 번의 루프를 돈 뒤에야 비로서 클라이언트 IP가 규칙에 적용되지 않음을 알게 된다. 반면 위 트리 구조는 최대 5 레벨의 트리 탐색으로 클라이언트 IP가 규칙에 적용되는지 여부를 알 수 있다.


결과물


어떤 식으로 구현했는지 공유하기에 앞서 실제 만들어 본 0.1 버전을 github에 올려 보았다. 아래 github 사이트에서 ip-filter의 사용법과 소스를 확인해 볼 수 있다.

다음에는


다음에 정리해 볼 내용은 아래와 같은 것들이 있다.



Posted by 최범균 madvirus

댓글을 달아 주세요